有很多无序的数,他们各不相等,怎么选出其中最大的若干个数呢?

解法1

我们首先想到的是将他们全部排序,可以使用快速排序,或者堆排序。平均复杂度是(nlogn),然后从后往前取出k个就是最大的k个数。

缺点是占用较大的内存。然后可以想题目只要求寻找最大的k个数,剩下的n-k个数不要求是排序的,甚至k个数也不要求有序,所以可以使用部分排序算法,比如选择排序或者交换排序,时间复杂度是:(nk),因为需要遍历k次。

//这里使用选择排序写一下代码
package com.kuiblog.寻找最大的k个数;

import java.util.Scanner;

public class Main1 {
    public static void main(String[] args) {
        Main1 main1 = new Main1();
        int[] arr = new int[] {2,1,3,4,7,6,8,9,4,10,11,20};
        main1.sort(arr, 5);
        for (int i = 0; i < 5; i++) {
            System.out.println(arr[i]);
        }
    }
    public void sort(int[] arr,int k) {
        //因为只需要k个数,所以循环k次将依次将最大的选出来就可以了
        int max;
        for (int i = 0; i < k; i++) {
            max = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]>arr[max]) {
                    max = j;
                }
            }
            //交换max和i
            swap(arr, max, i);
        }
    }
    public void swap(int[] arr,int m ,int n) {
        int temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
    }
}


解法2

上面部分排序感觉还可以,不过回忆一下快速排序,快排中的每一步都是讲数据分为两部分,其中后面的部分总是大于前面的部分,然后继续操作下去

假定N个数存储在数组S中,我们随机选出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中的元素小于等于X。那么这时候有两种可能

  • Sa中元素个数小于K,Sa中所有的数和Sb中最大的K-Sa个数,合起来就是最大的K个数

  • Sa中的元素个数大于K,直接在Sa中继续寻找K个元素

伪代码是:

Kbig(s,k):
    if(k <= 0)
          return [];
    if(s.length < k):
        return s;
    (Sa,Sb) = Partition(s);
     return Kbig(Sa,k).Append(Kbig(Sb,k-Sa.length));

Partition(S):
    Sa = [];
    Sb = [];
    swap = (S[1],S[Random()%S.length]);//打乱
    p = s[1];
    for i in [2:S.length]
          S[i]>p?Sa.Append(S[i]):Sb.Append(Sb);
    Sa.length < Sb.length?Sa.Append(p):Sb.Append(p);
    return (Sa,Sb);


解法3

寻找N个数中最大的K个数,本质就是寻找最大的K个数中最小的那个,也就是K大的书。可以使用二分搜索的策略。对于一个给定的数P,可以在O(n)的时间内好处所有不小于P的书。假定N个数中最大的数为Vmax,最小的为Vmin,则P肯定在Vmin到Vmax之间。可以在这个区间内二分搜索N个数中的第K个大数。

解法4

前面三个解法都需要对数据进行多次访问,有没有可能对数组访问一次就找到的。是的,可以利用最小堆的思想,就是利用容量为k的最小堆来存储最大的K个数。利用堆排序的思想,这个堆存储了k个数,如果遍历的数比堆顶小,可以忽略这个数;如果比堆顶大,把堆顶淘汰,加入这个数。

伪代码:

if(X>h[0]){
      h[0] = x ;//淘汰h[0];
      p = 0 ;
      while(p < k){
          q = 2 * p + 1;//左节点
          if(q+1<k && h[q+1] < h[q]){
              q = q+1;//在左右节点中找更小的那个
          }
          if(h[q] < h[p]){
              t = h[q];
              h[q] = h[p];
              h[p] = t;
              p = q;    //p落到下面
          }else{
              break;
          }
      }
}


解法5

如果所有N个数都是正整数,且他们的取值范围不大,可以考虑申请空间,记录每个证书出现的次数,然后再从大到小取K个。比如所有整数都在(0,maxn)之间的话,利用一个数组count[maxn]来记录每个数出现的个数,然后寻找k个元素

伪代码:

for(sumCount =0 , v= maxn - 1;v>=0;v--){
      sumCount += count(v);
      if(sumCont >=k){
        break;
    }
}
return v;