s4553711
8/8/2017 - 2:01 PM

215.cpp

class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int val = nums[right];
        for(int i = left; i < right; i++) {
            if (nums[i] < val) swap(nums[left++], nums[i]);
        }
        swap(nums[right], nums[left]);
        return left;
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size(), left = 0, right = len - 1, ans, pos = len - k;
        while((ans = partition(nums, left, right)) != pos) {
            ans < pos ? left = ans + 1 : right = ans - 1;
        }  
        return nums[len - k];
    }
};