Quick Select

    right   left

_____________|_________________

start end

class Solution {
public:
    /*
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    int kthLargestElement(int n, vector<int> &nums) {
        // write your code here
        if (nums.size() == 0) {
            return -1;
        }
        return select(nums, 0, nums.size() - 1, n);
    }
    int select (vector<int> &nums, int start, int end, int target) {
        if (start == end) {
            return nums[start];
        }
        int left = start;
        int right = end;
        int pivot = nums[(start+end)/ 2];

        while (left <= right) {
            while (left <= right && nums[left] > pivot) {
                left++;
            }
            while (left <= right && nums[right] < pivot) {
                right--;
            }
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        if (start + target - 1 <= right) {
            return select(nums, start, right, target);
        } else if (start + target - 1 >= left ) {
            return select(nums, left, end, target - (left - start));
        }
        return nums[right+1];
    }
};