尋求最大的k個數
方法一： 使用partition函數，將數組分為兩組。
(1)分為兩個組，sa和sb。
(2)若sa組的個數大于K，則繼續(xù)在sa分組中找取最大的K個數字 。
(3)若sa組中的數字小于K ，其個數為T，則繼續(xù)在sb中找取 K-T個數字 。
具體代碼實現：
#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 ; //表示第幾個位置
if(len == k)
return q ; //返回第k個位置
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 ;
} 方法二 ：
此種方法為常用方法，建立一個大小為K的堆。每次遍歷數組時，需要判斷是否需要加入堆中。
堆中存儲著的是最大的k個數字，但是若是需要插入堆中，則需要對堆進行調整時間為o(log k)。
全部的時間復雜度為o(n * log k)。
這種方法當數據量比較大的時候，比較方便。因為對所有的數據只會遍歷一次，第一種方法則會多次遍歷
數組。 如果所查找的k的數量比較大。可以考慮先求出k` ，然后再求出看k`+1 到 2 * k`之間的數字，然后
一次求取。
方法三：
利用二分的方法求取TOP k問題。
首先查找 max 和 min，然后計算出 mid = (max + min) / 2
該算法的實質是尋找最大的K個數中最小的一個。
代碼如下：
#include <iostream>
using namespace std ;
const int N = 8 ;
const int K = 4 ;
/**//*
利用二分的方法求取TOP k問題。
首先查找 max 和 min，然后計算出 mid = (max + min) / 2
該算法的實質是尋找最大的K個數中最小的一個。
*/
int find(int * a , int x) //查詢出大于或者等于x的元素個數
{
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之間只會存在一個或者多個相同的數字
{
while(max - min > 1) //max - min的值應該保證比兩個最小的元素之差要小
{
int mid = (max + min) / 2 ;
int num = find(a , mid) ; //返回比mid大的數字個數
if(num >= K) //最大的k個數目都要比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 ;
}