原題地址：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.

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

思路

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

代碼

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);
    }
};

這里貼一段自己以前學習的時候記錄的對于這種解法的更詳細的筆記

TIM截圖20170913091111.png

《算法導論》第9章更詳細地討論了這個問題，還介紹了一種最壞情況下運行時間為O(n)的算法，有空再補充。