leetcode076——数组中的第 k 大的数字

题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
 

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

思路：

最直观的解法是把数组排序后，输出length-k位置的数即可。但这样做肯定存在不必要的操作。

 快排算法可以参考：快慢指针实现快排

如何优化？

int findKthLargest(vector<int>& nums, int k) {
    quicksort(nums, 0, nums.size() - 1);
    return nums[nums.size() - k];
}

优化思路：

利用快排的思路，每一轮partition都会找到一个轴值对应排序后的位置，当这个轴值最后的位置是k的时候，就直接输出即可，不用做完所有比较，最好的情况就是每次轴值都在中值位，二分快排。

代码如下：

    int findKthLargest(vector<int>& nums, int k) {
        int start = 0, end = nums.size() - 1;
        int index = partition(nums, start, end);
        while(index != nums.size() - k) {
            if (index > nums.size() - k) {
                end = index - 1;
                index = partition(nums, start, end);
            } else if (index < nums.size() - k) {
                start = index + 1;
                index = partition(nums, start, end);
            }
        }

        return nums[index];
    }

    int swap(vector<int>& nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        return 0;
    }

    int partition(vector<int>& nums, int start, int end) {
        int index = (start + end) / 2;
        swap(nums, index, end);

        int small = start - 1;
        for (index = start; index < end; index++) {
            if (nums[index] < nums[end]) {
                ++small;
                if (small != index) {
                    swap(nums, small, index);
                }
            }
        }

        ++small;
        swap(nums, small, end);
        return small;
    }