寻找最大的K个数

寻找最大的K个数，这个是面试中比较常见的一道题，网上也有很多例子，在这里先写一些比较传统的解法，以后会更新到比较好的算法。
这个题拿到之后首先会想到排序，排好序之后在选取选取最大的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;
}
源码下载http://www.exceptionhelp.com/posts/539

评论

1 楼 mfkvfn 2014-04-10  

用不着这么复杂吧。应该跟寻找最大数一样的。寻找最大数一般

max=arr[0];
for(i=i;i<len;i++){
   if(arr[i]>max){
      max=arr[i];
   }
}

这个应该类似的办法就可以。

max=arr[0,K-1]
sort(max); //升序
for(i=K;i<len;i++){
   if(arr[k]>max[0]){
     max[0]=arr[k]; //删除max[0]，添加arr[i]
     sort(max);
   }
}
//输出max