无序整数数组查找第k个最大的数

速览

对于无序整数数组查找第k个最大的数，主要分为如下两种情况

  • 内存足够
    • 快排
    • 二分
      • 按数值区间二分
      • 按位二分
  • 内存不足
    • 堆排序（维护一个堆）
  • 数据范围取值不大
    • 键值索引

算法详解

内存足够

快排

算法思想

避免对所有数进行排序，采用快速排序分堆，并递归其中一半，直到所有＜val[pivot]的数量为k

伪代码

  1. int quickSort(int[]& num,int _begin,int _end){
  2.     int i=_begin,j=_end;
  3.     int pivot=num[0];
  4.     while(i<j){
  5.         while(i<j && num[j]<=pivot)    j--;
  6.         while(i<j && num[i]>pivot)    i++;
  7.         swap(num[i],num[j]);
  8.     }
  9.     swap(num[0],num[i]);
  10.     return i+1;
  11. }
  12. int FindKth(int[]& num,int k){
  13.     int n=num.size();
  14.     int curIdx=0;
  15.     int l=0,r=n-1;
  16.     while(curIdx!=k){
  17.         curIdx=quickSort(num,l,r);
  18.         if(curIdx<k){
  19.             l=curIdx+1;
  20.         }else if(curIdx>k){
  21.             r=curIdx-1;
  22.         }
  23.     }
  24.     return num[k-1];
  25. }

二分

划定中值区域，以二分法来找到第k个数所在的数值区间。

按数值区间二分

假设N个数的范围为[max_val,min_val],则第k个大的数一定在此区间

  1. /*  伪代码     */
  2. while(max_val-min_val>delta){
  3.     mid_val=min_val+(max_val-min_val)>>1;
  4.     if(count(num,mid_val)>k)
  5.         /* count() 返回num中>=mid_val的数量 */
  6.         min_val=mid_val;
  7.     else
  8.         max_val=mid_val;
  9. }
  11. /* 时间复杂度 */   O(N*log(N))

按位二分

假设元素范围均在【经典算法题】无序整数数组 - 图1,则由高位往地位比较，按1、0来分为两个部分，若1区间中整数个数cnt_1>=k，则在该区间中继续寻找第k大的数；否则在0区间中寻找第k=k-cnt_1个大的数。

内存不足

上述方法都需要将整个数组遍历一遍，当N非常大时（100亿），上述算法就适用了，故可采用数据结构——小根堆（C++中为优先队列），来解决上述问题。

小根堆

当K个数维护的根堆可存入内存时

  • 在小根堆中维护数组中前K个数，且假设根节点为第K个最大的值

  • 往根堆中插入后续元素

    • 当插入元素>根节点时,删除根节点，并存入插入元素
    • 否则，忽略

      当K个数维护的根堆不能存入内存时（K过大，10亿）

  • 建立一个大小为K'的小根堆（该根堆可放入内存）,并维护一个计数器cnt=K'

  • 往根堆中插入元素直到cnt==K'
    • 当插入元素>根节点时,删除根节点，并存入插入元素；cnt++
    • 否则,cnt++