在N个乱序数字中查找第k大的数字

在N个乱序数字中查找第k大的数字，时间复杂度可以减小至

O(N*logN)
O(N)
O(1)
O(2)

答案：B

所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。

注意：

题中

只需

得到最大的K个数，而

不需要

对后面N-K个数排序

可能存在的条件限制：

要求时间和空间消耗最小、海量数据、待排序的数据可能是浮点数等

方法一：对所有元素进行排序，之后取出前K个元素，不提倡使用

思路：

使用最快排序算法，选择快排或堆排

时间复杂度：O(n*logn) + O(K) = O(n*logn)

特点：

需要对全部元素进行排序，K = 1 时，时间复杂度也为O(n*logn)

方法二：只需要对前K个元素排序，不需要对N-K个元素进行排序，不提倡使用

思路：

使用选择排序或起泡排序，进行K次选择，可得到第k大的数

时间复杂度：O(n*k)

方法三：不对前K个数进行排序 + 不对N-k个数排序，可以使用

思路：

寻找第K个大元素。

具体方法：使用类似快速排序

，

执行一次快速排序后，每次只选择一部分继续执行快速排序，直到找到第K个大元素为止，此时这个元素在数组位置后面的元素即所求

时间复杂度：

若随机选取枢纽，线性期望时间O(N)

若选取数组的“中位数的中位数”作为枢纽，最坏情况下的时间复杂度O（N）

利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。

利用快排的partion思想 T(n) = 2T(n/2) + O(1) 时间复杂度为O(n)

该方法只有当我们可以修改输入的数组时可用，位于数组左边的k个数字就是最小的k个数字（但这k个数字不一定是排序的），位于

第k个数右边的数字都比第k个数字大

         [cpp]

         view plain

          copy

          //这里实现的是解法3

          #include<iostream>

          #include<stdio.h>

          using

          namespace

          std;

          int

          Partition (

          int

          *L,

          int

          low,

          int

          high)

         {

          int

          temp = L[low];

          int

          pt   = L[low];

          //哨兵

          while

          (low != high)

         {

          while

          (low < high && L[high] >= pt)

         high–;

         L[low] = L[high];

          while

          (low < high && L[low] <= pt)

         low++;

         L[high] = L[low];

         }

         L[low] = temp;

          return

          low;

         }

          void

          QSort (

          int

          *L,

          int

          low,

          int

          high)

          //快速排序

         {

          int

          pl;

          if

          (low < high)

         {

         pl = Partition (L,low,high);

         QSort (L, low,  pl-1);

         QSort (L, pl+1, high);

         }

         }

          void

          findk(

          int

          k,

          int

          *L,

          int

          low,

          int

          high)

         {

          int

          temp;

         temp=Partition(L,low,high);

          if

          (temp==k-1)

         {

         cout<<

          “第”

          <<temp+1<<

          “大的数是:”

          <<L[temp]<<endl;

         }

          else

          if

          (temp>k-1)

         findk(k,L,low,temp-1);

          else

         findk(k,L,temp+1,high);

         }

          int

          main()

         {

          int

          a[10]={15,25,9,48,36,100,58,99,126,5},i,j,k;

         cout<<

          “排序前：”

          <<endl;

          for

          (i=0;i<10;i++){

         cout<<a[i]<<

          ” ”

          ;

         }

         cout<<endl;

         cout<<

          “请输入你要查找第k大的数：”

          <<endl;

         cin>>k;

         findk(k,a,0,9);

          //查找第k大的数不需要全部排序

         QSort(a,0,9);

         cout<<

          “排序后：”

          <<endl;

          for

          (i=0;i<10;i++){

         cout<<a[i]<<

          ” ”

          ;

         }

         cout<<endl;

         system(

          “Pause”

          );

          return

          0;

         }

方法四、我们寻找线性查找的算法，适合数据量小的数据

思路1：寻找第K个大的元素 + 计数排序 + 数组实现

具体方法：

使用计数排序，另开辟一个数组，记录每个整数出现的次数，然后再从大到小取最大的 K 个。

缺点：

1、有些数没有出现过，仍要为其保留一个空间，空间浪费比较严重

2、不能处理浮点数

思路2：寻找第K个大的元素 + 计数排序 + map实现

具体方法：

利用STL最后的map保存每一个元素Si出现的次数，之后从大到小扫描找到K个数

时间复杂度O(n*logn) 空间复杂度O(n)

注意：

1、可以处理浮点数

2、不能使用CMap实现，因为Cmap不能根据key自动为其排序

3、map内部是由红黑树实现的，每次插入都是logn，总的复杂度为n*logn。

这里给出两个另外的思路，他们没有计数排序和类快速排序好，这里仅仅为了打开思路

方法五、基数排序，不提倡使用

思路：

寻找第K个大的元素 + 基数排序

一次遍历，找到最大的数为Vmax;，最小的数为Vmin

对区间[Vmin,Vmax]分成M块

每个小区间的跨度为d=（Vmax–Vmin）/M

即 [Vmin,Vmin+d], [Vmin+d,Vmin+ 2d],……

扫描一遍所有元素，统计各个小区间中的元素个数,我们可以知道第K大的元素在哪一个小区间。

然后，再对那个小区间，继续进行分块处理。

。。。。递归下去，一直找到一个区间只含第K个数为止

时间复杂度：O ( (N +M )* log2 M (|V max – V min |/delta) )

方法六、类二分查找，不提倡使用

思路：

寻找第K个大的元素 + 类二分查找

二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

         [cpp]

         view plain

          copy

          while

          (Vmax – Vmin > delta)

         {

         Vmid = Vmin + (Vmax – Vmin) * 0.5;

          if

          (f(arr,N,Vmid) >= K)

         Vmin = Vmid;

          else

         Vmax = Vmid;

         }

         伪码中f（arr ,N,Vmid）返回数组arr [0, …, N-1]中大于等于Vmid的数的个数。

举例

结果分析：程序运行的结果，得到一个区间（Vmin, Vmax），这个区间仅包含一个元素（或者多个相等的元素）这个元素就是第K大的元素。

注意：

1、delta的取值要比任意两个不相等的元素差值之最小值小。如果所有元素都是整数，delta可以取值0.5。

2、算法的时间复杂度O( N * log2 (|Vmax – Vmin| /delta) ) – 不知道怎么算的

方法七、我们要尽可能少的遍历所有数据。相比下，属于较好的算法，提倡使用

思路：维护一个大小为k的小根堆，堆顶元素是最大K 个数中最小的一个，即第K个元素

处理过程对于数组中的每一个元素X，判断与堆顶的大小

如果X 比堆顶小，则不需要改变原来的堆, 因为这个元素比最大的K 个数小。

如果X比堆顶大，要用X 替换堆顶的元素Y 。调整堆的时间复杂度为O(log2K)。

时间复杂度： O (N * log2 K )，算法只需要扫描所有的数据一次

空间复杂度：大小为K的数组，只需要存储一个容量为K 的堆。

注意、大多数情况下，堆可以全部载入内存。如果K 仍然很大，我们可以尝试先找最大的K ’个元素，然后找第K ’+1个到第2 * K ’

元素，如此类推（其中容量K ’的堆可以完全载入内存）。这时，每求出K’个数，就遍历一遍数据了

方法八、可以直接对原数组建立大根堆，取这个优先队列前k个值。数据量小的时候可以考虑

思路：在线性时间内，能将一个无序的数组建成一个最小堆，然后取堆中的前k个数

建堆时间是O（n），每次调整时间为O(log n)

复杂度O(n)+k*O(log n)

在有优化，每次调整时不需要调整logn次了，只需调整K次，这个k 和取第k个数是同一个数

也就是，建堆后，直接取出第一个最大值。取第一个最大值后，大根堆已经被破坏了，之后需要向下进行k次调整就好。取第2个最大值后，之后进行k-1次调整，等等。注意，每次取完值后，这个堆就不是大根堆了

原来堆的方法，每次调整l最大是logn次，调整后仍是大根堆

优化后的时间复杂度是O(n+k^2)

评价：

这两个方法的时间复杂度都比维护一个大小为k的小根堆的方法好，但是后者是空间复杂度还是很好的，内存中只需维护一个大小为k堆，而其他两个方法需要把整个堆都放入内存，这对于处理海量数据效率还是不是很好啊，而且作者July还在程序验证过，其实这两种算法在时间上区别不是很大。

扩展题目<转别人的，还没有总结>

1. 如果需要找出N个数中最大的K个不同的浮点数呢？比如，含有10个浮点数的数组（1.5，1.5，2.5，3.5，3.5，5，0，-1.5，3.5）中最大的3个不同的浮点数是（5，3.5，2.5）。

解答：

上面的解法

除了

寻找第K个大的元素 + 计数排序 + 数组实现

均适用

2. 如果是找第k到第m（0<k<=m<=n)大的数呢？

解答：

如果把问题看做m-k+1个第k大问题，则前面解法均适用。但是对于类似前k大这样的问题，最好使用解法5或者解法7，总体复杂度较低。

3. 在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算法要如何变动以达到快速更新（incremental update）并及时返回权重最大的K个网页？

提示：堆排序？当每一个网页权重更新的时候，更新堆。还有更好的方法吗？

解答：

要达到快速的更新，我们可以解法8,(对原数组简历大根堆)，使用映射二分堆，可以使更新的操作达到O(logn)

4. 在实际应用中，还有一个“精确度”的问题。我们可能并不需要返回严格意义上的最大的K个元素，在边界位置允许出现一些误差。当用户输入一个query的时候，对于每一个文档d来说，它跟这个query之间都有一个相关性衡量权重f (query, d)。搜索引擎需要返回给用户的就是相关性权重最大的K个网页。如果每页10个网页，用户不会关心第1000页开外搜索结果的“精确度”，稍有误差是可以接受的。比如我们可以返回相关性第10 001大的网页，而不是第9999大的。在这种情况下，算法该如何改进才能更快更有效率呢？网页的数目可能大到一台机器无法容纳得下，这时怎么办呢？

提示：归并排序？如果每台机器都返回最相关的K个文档，那么所有机器上最相关K个文档的并集肯定包含全集中最相关的K个文档。由于边界情况并不需要非常精确，如果每台机器返回最好的K’个文档，那么K’应该如何取值，以达到我们返回最相关的90%*K个文档是完全精确的，或者最终返回的最相关的K个文档精确度超过90%（最相关的K个文档中90%以上在全集中相关性的确排在前K），或者最终返回的最相关的K个文档最差的相关性排序没有超出110%*K。

你可能也喜欢