【Leetcode】Kth Largest Element in an Array

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.

For example

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

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

使用快速排序的思想，对于一个数组先取一个pivot（我一般都取子数组的第一个数字为pivot），然后将数组分割为两个部分，分别是大于pivot的（放在左边）和小于pivot的（放在右边）。例如比pivot大的数字有3个，则pivot是整个数组中第4大的数字。利用这种方法对数组进行分割，把比pivot大的放在左边，比pivot小的放在右边（从大到小排序），然后返回划分点的位置，若返回位置大于k - 1，则要求找的数字在左半边，在左边继续寻找，反之则在右边继续寻找。

例如对数组5, 7, 6, 2, 9, 1找第3大的数字，以数字5为pivot，进行第一轮的划分后，数组变为7, 6, 9, 5, 2, 1,则返回的位置为3（数组从0开始），则3 > 3 - 1，则说明要找的第三大的数在左边，即在7, 6, 9中间寻找。

时间复杂度：
虽然用的是快排的方法，但是它与快排不同的地方在于，每次对数组分为两半时，会把另外一半砍掉，只对其中的一半进行查找，然后再分再舍弃，如下图所示，所以整个数划出来，其实走的路线只有一条，其他的都被丢掉了。因此最后的时间复杂度为T(n)。

伪代码如下：

int partition(int* nums, int left, int right) {
    int pivot = nums[left];
    int l = left + 1, r = right;
    int t;
    while (l <= r) {  // 等号是对最后一个数也要进行分类，是分左边或右边
        if (nums[l] < pivot && nums[r] > pivot) {
            t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
            l++;
            r--;
        }
        else if (pivot <= nums[l])  l++;
        else if (pivot >= nums[r])  r--;
    }

    t = nums[left];
    nums[left] = nums[r];
    nums[r] = t;

    return r;  // 最后返回的，是pivot应该放置的位置，保证左边都是大的，右边都是小的
}

int findKthLargest(int* nums, int numsSize, int k) {
    int left = 0, right = numsSize - 1;
    while(true) {
        int pos = partition(nums, left, right);
        if (pos == k-1)
            return nums[pos];
        else if (pos < k-1)
            left = pos + 1;
        else if (pos > k-1)
            right = pos - 1;
    } 
}