Find K-th largest element in an array.

Notice

You can swap elements in the array

Have you met this question in a real interview?

Yes

Example

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

In array[1,2,3,4,5], the 1st largest element is5, 2nd largest element is4, 3rd largest element is3and etc.

Challenge

O(n) time, O(1) extra memory.

line 17, kth largest , count from the end if it's in ascending order.

partition, needs to swap first on line 34 ,then swap again on line 44

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

    int start = 0, end = nums.size\(\) - 1;

    while \(true\) {

        if \(start > end\) {

            break;

        }

        int left = start, right = end;

        int pivot = nums\[\(left + right\) / 2\];

        while \(left <= right\) {

            while \(left <= right && nums\[left\] > pivot\) {

                ++left;

            }

            while \(left <= right && nums\[right\] < pivot\) {

                --right;

            }

            if \(left <= right\) {

                swap\(nums\[left++\], nums\[right--\]\);

            }

        }

        if \(k - 1 <= right\) {

            end = right;

        } else if \(k - 1 >= left\) {

            start = left;

        } else {

            return pivot;

        }

    }

    return -1;

}

};