215-kth-largest-element-in-an-array.md

215. Kth Largest Element in an Array - 数组中的第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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

---

题目标签：Heap / Divide and Conquer

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	33 ms	36.3 MB

class Solution {
    public int partition(int[] nums, int k, int st, int ed) {
        if (st > ed || k > nums.length) return -1;

        int left = st;
        int right = ed;
        int pivot = st;
        
        while (left < right) {
            while (left < right && nums[right] <= nums[pivot]) 
                right--;
            while (left < right && nums[left] >= nums[pivot])
                left++;
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        int tmp = nums[left];
        nums[left] = nums[pivot];
        nums[pivot] = tmp;

        if (left > k - 1) {
            partition(nums, k, st, left - 1);
        }
        if (left < k - 1) {
            partition(nums, k, left + 1, ed);
        }
        return nums[k - 1];
    }
    
    public int findKthLargest(int[] nums, int k) {
        return partition(nums, k, 0, nums.length - 1);
    }
}