一组N个数,确定其中抵第k个最大值

来源:转载

首先,这个问题的最容易想到的就是冒泡排序。先把N个数存入数组中,之后 用冒泡算法从大到小排序,在取k位置的值。

具体求解过程如下:

import java.util.Random;public class MaxK{static int[] nums = new int[20];static Random rand = new Random(4);public static void main(String[] args){int k = Integer.parseInt(args[0]);init();printNums(nums);int[] sortBubble = bubbleSort(nums);printNums(sortBubble);System.out.println(sortBubble[k - 1]);}static void printNums(int[] nums){for(int i = 0, len = nums.length; i < len; i++)System.out.print(nums[i] + " ");System.out.println();}static void init(){for(int i = 0; i < 20; i++)nums[i] = rand.nextInt(100);}static int[] bubbleSort(int[] nums){int arrLen = nums.length;int[] bubble = new int[arrLen];System.arraycopy(nums, 0, bubble, 0, arrLen);for(int i = 0; i < arrLen; i++){int tk = bubble[i];int tkj = i + 1;for(int j = i + 1; j < arrLen; j++){if(bubble[j] > tk){tk = bubble[j];tkj = j;}}if(tk > bubble[i]){int temp = bubble[i];bubble[i] = bubble[tkj];bubble[tkj] = temp;}}return bubble;}}

还有稍微好一些的算法,就是先把前k个元素读入数组,再对其排序(递减)。接着逐个对比剩下的元素,将符合的元素插入k数组,调整k数组。

static int maxK(int lk){// 求第lk大的数值int[] karr = new int[lk];System.arraycopy(nums, 0, karr, 0, lk);int[] bubbledKarr = bubbleSort(karr);int rek = bubbledKarr[lk - 1];for(int i = lk; i < 20; i++){ //20是nums长度,判断剩下的元素if(nums[i] > bubbledKarr[lk -1]){int loc = lk -2;for(; loc >=0 ; loc--)if(nums[i] < bubbledKarr[loc])break;loc++; //定位插入元素位置int[] temp = new int[lk - loc];//需要调整的k数组的值System.arraycopy(bubbledKarr, loc, temp, 0, lk - loc);bubbledKarr[loc] = nums[i];System.arraycopy(temp, 0, bubbledKarr, loc + 1, lk - loc -1);//调整替换元素之后的k数组}}return bubbledKarr[lk - 1];}



分享给朋友:
您可能感兴趣的文章:
随机阅读: