尋求最大的k個(gè)數(shù)
方法一： 使用partition函數(shù)，將數(shù)組分為兩組。
(1)分為兩個(gè)組，sa和sb。
(2)若sa組的個(gè)數(shù)大于K，則繼續(xù)在sa分組中找取最大的K個(gè)數(shù)字 。
(3)若sa組中的數(shù)字小于K ，其個(gè)數(shù)為T(mén)，則繼續(xù)在sb中找取 K-T個(gè)數(shù)字 。
具體代碼實(shí)現(xiàn)：
#include <iostream>
using namespace std ;
const int N = 8 ;
const int K = 4 ;
int partition(int a[] ,int low , int high)
{
int i = low - 1 ;
int j = low;
while(j < high)
{
if(a[j] >= a[high])
{
swap( a[i+1] , a[j]) ;
i++ ;
}
j++ ;
}
//最后處理a[high]
swap(a[i+1] , a[high]) ;
return i + 1;
}
int findk(int a[] , int low , int high , int k)
{
if(low < high)
{
int q = partition(a , low , high) ;
int len = q - low + 1 ; //表示第幾個(gè)位置
if(len == k)
return q ; //返回第k個(gè)位置
else if(len < k)
return findk(a , q + 1 , high , k - len) ;
else
return findk(a , low , q - 1, k ) ;
}
}
int main()
{
int a[N] = {5 ,2 ,66 ,23, 11 ,1 ,4 ,55} ;
findk(a , 0 , N - 1 , K) ;
for(int i = 0 ; i < K ; i++)
cout<<a[i]<<endl ;
system("pause") ;
return 0 ;
} 方法二 ：
此種方法為常用方法，建立一個(gè)大小為K的堆。每次遍歷數(shù)組時(shí)，需要判斷是否需要加入堆中。
堆中存儲(chǔ)著的是最大的k個(gè)數(shù)字，但是若是需要插入堆中，則需要對(duì)堆進(jìn)行調(diào)整時(shí)間為o(log k)。
全部的時(shí)間復(fù)雜度為o(n * log k)。
這種方法當(dāng)數(shù)據(jù)量比較大的時(shí)候，比較方便。因?yàn)閷?duì)所有的數(shù)據(jù)只會(huì)遍歷一次，第一種方法則會(huì)多次遍歷
數(shù)組。 如果所查找的k的數(shù)量比較大。可以考慮先求出k` ，然后再求出看k`+1 到 2 * k`之間的數(shù)字，然后
一次求取。
方法三：
利用二分的方法求取TOP k問(wèn)題。
首先查找 max 和 min，然后計(jì)算出 mid = (max + min) / 2
該算法的實(shí)質(zhì)是尋找最大的K個(gè)數(shù)中最小的一個(gè)。
代碼如下：
#include <iostream>
using namespace std ;
const int N = 8 ;
const int K = 4 ;
/**//*
利用二分的方法求取TOP k問(wèn)題。
首先查找 max 和 min，然后計(jì)算出 mid = (max + min) / 2
該算法的實(shí)質(zhì)是尋找最大的K個(gè)數(shù)中最小的一個(gè)。
*/
int find(int * a , int x) //查詢(xún)出大于或者等于x的元素個(gè)數(shù)
{
int sum = 0 ;
for(int i = 0 ; i < N ; i++ )
{
if(a[i] >= x)
sum++ ;
}
return sum ;
}
int getK(int * a , int max , int min) //最終max min之間只會(huì)存在一個(gè)或者多個(gè)相同的數(shù)字
{
while(max - min > 1) //max - min的值應(yīng)該保證比兩個(gè)最小的元素之差要小
{
int mid = (max + min) / 2 ;
int num = find(a , mid) ; //返回比mid大的數(shù)字個(gè)數(shù)
if(num >= K) //最大的k個(gè)數(shù)目都要比min值大
min = mid ;
else
max = mid ;
}
cout<<"end"<<endl;
return min ;
}
int main()
{
int a[N] = {54, 2 ,5 ,11 ,554 ,65 ,33 ,2} ;
int x = getK(a , 554 , 2) ;
cout<<x<<endl ;
getchar() ;
return 0 ;
}