Kth Largest Element in an Array

LeetCode #215

Description:

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.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Example:

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Idea:

就是用quickselect的方法，跟quicksort很类似。

Time: O(n).

Code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        int result = quickSelect(nums, 0, nums.size()-1, k);

        return result;

    }

    int quickSelect(vector<int>& nums, int p, int q, int k){
        if(k>0 && k <= q-p+1){
            int r = partition(nums, p, q);
            if(r - p == k-1) return nums[r];
            else if(r - p > k-1) return quickSelect(nums, p, r-1, k);
            else return quickSelect(nums, r+1, q, k - (r-p + 1) );

        }
        return INT_MAX;
    }

    int partition(vector<int>& nums, int p, int q){
        int i = p-1;
        int last = q;
        for(int j=p; j<q; ++j){
            if(nums[j] > nums[last]){
                swap(nums[j], nums[++i]);
            }
        }
        swap(nums[++i], nums[last]);
        return i;
    }
};