TOP-K問題（c++實作）

@TOP-K問題（c++實作）

問題描述：

給定一個數組，找出數組中最大的K個數或者最小的K個數，稱為top K問題。這是面試的常考題，解法可以是基于最大堆/最大堆排序、基于快速排序實作等等，文本基于快速排序的思想實作。

算法思路：

我們不會采用快速排序的算法來實作TOP-K問題，但我們可以利用快速排序的思想，在數組中随機找一個元素pivot，将數組分成兩部分Sa和Sb，其中Sa的元素>=pivot，Sb的元素<pivot，然後分析兩種情況：

若Sa中元素的個數大于或等于k，則在Sa中查找最大的k個數

若Sa中元素的個數小于k，其個數為len，則在Sb中查找k-len個數字

如此遞歸下去，不斷把問題分解為更小的問題，直到求出結果。注意，這裡遞歸的原子就是在[a,b]中查找n個數字

該算法的平均時間複雜度為O(N * logk)。以求K大的數為例，算法實作如下：

代碼

#include <iostream>
#include <vector>
using namespace std;
//這個和快速排序中的partion是相同的
int partion(vector<int> &a,int left,int right){
    int i = left - 1;
    int x = a[right-1];
    int p = left;
    for(int j = p;j<right;j++ ){
        if(a[j-1] < x){
            i = i + 1;
            swap(a[i-1],a[j-1]);
        }
    }
    swap(a[i],a[right-1]);
    return i+1;
}

int topk(vector<int> &a,int left, int right, int k){
    int index = -1;
    if(left < right){
        int pos = partion(a,left,right);
        int len = right - pos+1;
        if(len == k)
            index = pos;
        else if (len < k){
            index = topk(a,left,pos-1,k-len);
        }
        else {
        index = topk(a,pos+1,right,k);
        }
    }
    return index;
}

int main(){
    int b[] = {1,8,5,9,6};
    vector<int> a(b,b+5);
    int l = a.size();
    int k =4;
    cout << "原數組為：";
    for(int i=0;i<l;i++){
        cout << a[i] <<" ";
    }
    cout << endl;
    int inde = topk(a,1,l,k);
    cout << "TOP-K 為：";
    for (int i=inde;i<=l;i++){
        cout << a[i-1] <<" ";
    }
    cout <<endl;
}
           

結果：