Kth Largest Element

Kth Largest Element

Find K-th largest element in an array.

Note

You can swap elements in the array

Example

In array [9,3,2,4,8], the 3rd largest element is 4

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Challenge

O(n) time, O(1) space

---------------------- thinking -----------------------
http://codeanytime.blogspot.com/2014/12/lintcode-kth-largest-element.html
---------------------- codes -------------------------
class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        if (nums.size() == 0 || k == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.size() - 1;
        while (start + 1 < end) {
            int i = start + 1;
            int j = end;
            while (i <= j) {
                if (nums[i] < nums[start]) {
                    i++;
                } else if (nums[j] > nums[start]) {
                    j--;
                } else {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++;
                    j--;
                }
            }
            int tmp = nums[j];
            nums[j] = nums[start];
            nums[start] = tmp;
            if (k == end - j + 1) {
                return nums[j];
            } else if (k > end - j + 1) {
                k = k - (end - j) - 1;
                end = j-1;
            } else {
                start = j+1;
            }
        }
        int small = nums[start] < nums[end]?nums[start]:nums[end];
        int big = nums[start] < nums[end]?nums[end]:nums[start];
        if (k == 1) return big;
        return small;
    }
};