当前位置： 移动技术网 > IT编程>开发语言>Java > JAVA中寻找最大的K个数解法

JAVA中寻找最大的K个数解法

2019年07月22日  | 移动技术网IT编程  | 我要评论

这个题拿到之后首先会想到排序，排好序之后在选取选取最大的k个数。排序选择快速排序是个比较好的选择。
好了，让我们来进行第一个解法：快速排序
代码如下
复制代码 代码如下:

public static void quicksort(int[] arr, int start, int end) {
  if (start < end) {
   int key = arr[start];
   int right = start;
   int left = end;
   while (right < left) {
    while (right < left && arr[left] > key) {
     left --;
    }
    if (right < left) {
     arr[right] = arr[left];
    }
    while (right < left && arr[right] <= key) {
     right ++;
    }
    if (right < left) {
     arr[left] = arr[right];
    }
   }
   arr[right] = key;
   quicksort(arr, start, right-1);
   quicksort(arr, left+1, end);
  }
 }
 

快速排序之后，数组会是有序的，上面的排序是从小到大的，所以我们输出应该是下面这样
复制代码 代码如下:
                int k = 4;
  for (int i=arr.length-1; i>=arr.length-k; i--) {
   system.out.println(arr[i]+"  ");
  }

。第一个解法已经好了，但是有没有更好的办法。
答案是有的！我们可以选择部分排序，接下来我们使用选择排序来做解决这个问题。
代码如下：
复制代码 代码如下:
public static int[] selectsortk(int[] arr, int k) {
  if(arr == null || arr.length == 0) {
   return null;
  }
  int[] newarr = new int[k];
  list<integer> list = new arraylist<integer>();//记录每次最大数的下标
  for (int i=0; i<k; i++) {
   int maxvalue = integer.min_value; //最大值
   int maxindex = i;
   for (int j=0; j<arr.length; j++) {
    if (arr[j] > maxvalue && !list.contains(j) ) {
     maxvalue = arr[j];
     maxindex = j;
    }
   }
   if (!list.contains(maxindex)) {//如果不存在，就加入
    list.add(maxindex);
    newarr[i] = maxvalue;
   }
  }
  return newarr;
 }

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网