题目描述

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.

样例

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

算法

(快排) $O(nlogn)$ $partition解法$

C++ 代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        if(n==0||n<k)return 0;
        int left=0,right=n-1;
        while(1){
            int pos=partition(nums,left,right);
            if(pos+1==k)
                return nums[pos];
            else if(pos+1>k){
                right=pos-1;
            }
            else{
                left=pos+1;
            }
        }
    }
    int partition(vector<int>&nums,int start,int end){
        int pivot=nums[start],begin=start;
        start=start+1;
        while(start<=end){
            if(nums[start]<pivot&&nums[end]>=pivot){
                swap(nums[start++],nums[end--]);
            }
            else if(nums[start]>=pivot){
                start++;
            }
            else if(nums[end]<pivot){
                end--;
            }
        }
        swap(nums[begin],nums[end]);//把大于等于pivot的与nums[begin]交换，这时候前面所有都大于等于pivot
        return end;
    }
};