原題地址：https://leetcode.com/problems/kth-largest-element-in-an-array/description/

題目描述

215.Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, >not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

大意：找出所給數(shù)組里第k大的元素。

思路

用快速排序里的Partition部分來實(shí)現(xiàn)不斷縮小這個(gè)問題的規(guī)模直到找到目標(biāo)元素。
快速排序里的Partition函數(shù)會(huì)找到一個(gè)pivot元素，然后小于或等于這個(gè)pivot元素的值被放置在pivot的一側(cè)，大于pivot元素的值被放在另一側(cè)。也即，pivot元素的下標(biāo)就能反映它的大小在整個(gè)數(shù)組里排第幾位。
應(yīng)用到本題里，將比pivot元素大的數(shù)都放在pivot的左側(cè)，pivot的下標(biāo)加上1就是pivot元素大小的排名（題目要找第k個(gè)元素，k從1開始，而下標(biāo)從0開始）。再根據(jù)k和pivot下標(biāo)的大小情況來決定是直接返回當(dāng)前的pivot，或是在pivot元素的左側(cè)右側(cè)進(jìn)行遞歸處理。

代碼

class Solution {
public:
    
    int Partition(vector<int>& nums,int start,int end){
        if(start==end){
            return start;
        }
        int pivot_value = nums[start];
        int split=start+1;
        for(int i=start+1;i<=end;i++){
            if(nums[i]>pivot_value){
                int temp = nums[i];
                nums[i] = nums[split];
                nums[split]=temp;
                split++;
            }else{
            //pass
            }
        }
        int temp =nums[start];
        nums[start] = nums[split-1];
        nums[split-1]=temp;
        return split-1;
    }
    
    int  RealFind(vector<int>& nums,int k,int start,int end ){
        int pivot = Partition(nums,start,end);
        if(pivot==k){
            return nums[pivot];
        }else if(pivot>k){
            return RealFind(nums,k,start,pivot-1);
        }else{
            return RealFind(nums,k,pivot+1,end);
        }
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return RealFind(nums,k-1,0,nums.size()-1);
    }
};

這里貼一段自己以前學(xué)習(xí)的時(shí)候記錄的對(duì)于這種解法的更詳細(xì)的筆記

TIM截圖20170913091111.png

《算法導(dǎo)論》第9章更詳細(xì)地討論了這個(gè)問題，還介紹了一種最壞情況下運(yùn)行時(shí)間為O(n)的算法，有空再補(bǔ)充。