Top K

topk.md

##Top K 问题

###Methods

• Top K问题可以维护一个堆，以O(n*logk)的复杂度完成
• Top K问题可以用类似于快排Partition的过程递归的解决
• Top K问题使用STL nth_element解决（大幅缩减代码）

###Complexity

• Partition_select过程已被证明可以获得O(n)的平均复杂度
• STL nth_element的内部实现采用了随机版本，所以可以获得比取右边元素为pivot更好的平均复杂度

###Code

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int Partition(vector<int> &data, int left, int right)     
    {   //Pivot data[right]
        int i = left - 1, j = left;
        for (; j < right; ++j)   
        {   
            if (data[j] < data[right])
            {   
                ++i;   
                swap(data[i], data[j]);   
            }   
        }   
        ++i;   
        swap(data[i], data[right]);   
        return i;
    }   
      
    void FindKLeast(vector<int> &data, int left, int right, int k)     
    {   
        if (left < right)   
        {   
            int midId = Partition(data, left, right);      
            /*
    		Left side contains all k elements
    		*/
            if (midId > k)   
            {   
                FindKLeast(data, left, midId - 1, k);
            }    
            /*
    		Right side contains |left| - k elements 
    		*/
            else   
            {   
                if (midId < k)   
                {   
                    FindKLeast(data, midId + 1, right, k);
                }   
            }   
        }   
    }  
    void FindKLeastNumbers1(vector<int> &data, unsigned int k)   
    {   
        int len = data.size();   
        if (k > len)   
        {   
            throw new std::exception("Invalid argument!");   
        }   
        FindKLeast(data, 0, len - 1, k); 
    }  
    
    void FindKLeastNumbers2(vector<int>& data,int k)
    {
    	nth_element(data.begin(),data.begin()+k,data.end());
    }
    
    int main()
    {
    	int a[11] = {22,30,30,17,33,40,17,23,22,12,20};
    	/*
    	Testing data
    	*/
    	vector<int> test1(a,a+11);
    	vector<int> test2(a,a+11);
    	
    	int k = 5;
    	
    	FindKLeastNumbers1(test1,k);
    	FindKLeastNumbers2(test2,k);
    
    	vector<int> result1(k,0);
    	vector<int> result2(k,0);
        //copy result
    	copy(test1.begin(),test1.begin()+k,result1.begin());
    	copy(test2.begin(),test2.begin()+k,result2.begin() );
    	system("pause");
    	return 0;
    }