LeetCode 题解之 215. Kth Largest Element in an Array-蒲公英云

LeetCode 题解之 215. Kth Largest Element in an Array

Kth Largest Element in an Array
题目描述和难度
题目描述：
在未排序的数组中找到第 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 ≤ 数组的长度。

题目难度：中等。
英文网址：215. Kth Largest Element in an Array 。
中文网址：215. 数组中的第K个最大元素。
思路分析
求解关键：这是一个常规问题，使用借用快速排序的 partition 的思想完成。关键在于理解 partition 的返回值，返回值是拉通了整个数组的索引值，这一点是非常重要的，不要把问题想得复杂了。

partition 这个函数返回的是整个数组的第 k 个最小元素（从 0 开始计算）。
如果找第 k 个最小元素，即第 n - k 个最大元素。
例如：给定数组为：[2,5,6,1,4,7] ，一共 6 个元素找 k = 2，如果返回 4 ，就可以返回了。
给定数组为：[2,5,6,1,4,7] ，一共 6 个元素找 k = 2，如果返回 2 ，左边的区间就可以不用看了。

参考解答
参考解答1：使用快速排序的 partition 的思想完成。
public class Solution2 {

private static Random random = new Random(System.currentTimeMillis());
public int findKthLargest(int\[\] nums, int k) \{  
    int len = nums.length;  
    if (len == 0 || k > len) \{  
        throw new IllegalArgumentException("参数错误");  
    \}  
    // 转换一下，这样比较好操作  
    // 第 k 大元素的索引是 len - k  
    int target = len - k;  
    int l = 0;  
    int r = len - 1;  
    while (true) \{  
        int i = partition(nums, l, r);  
        if (i < target) \{  
            l = i + 1;  
        \} else if (i > target) \{  
            r = i - 1;  
        \} else \{  
            return nums\[i\];  
        \}  
    \}  
\}
// 在区间 \[left, right\] 这个区间执行 partition 操作  
private int partition(int\[\] nums, int left, int right) \{  
    // 在区间随机选择一个元素作为标定点（以下这两行代码非必需）  
    // 这一步优化非必需  
    if (right > left) \{  
        int randomIndex = left + 1 + random.nextInt(right - left);  
        swap(nums, left, randomIndex);  
    \}
    int pivot = nums\[left\];  
    int l = left;  
    for (int i = left + 1; i <= right; i++) \{  
        if (nums\[i\] < pivot) \{  
            l++;  
            swap(nums, l, i);  
        \}  
    \}  
    swap(nums, left, l);  
    return l;  
\}
private void swap(int\[\] nums, int index1, int index2) \{  
    if (index1 == index2) \{  
        return;  
    \}  
    int temp = nums\[index1\];  
    nums\[index1\] = nums\[index2\];  
    nums\[index2\] = temp;  
\}

}
参考解答2：使用最小堆，这个写法是我最开始的写法，有点死板。
public class Solution3 {

public int findKthLargest(int\[\] nums, int k) \{  
    int len = nums.length;  
    if (len == 0 || k > len) \{  
        throw new IllegalArgumentException("参数错误");  
    \}  
    // 使用一个含有 k 个元素的最小堆  
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (a, b) -> a - b);  
    for (int i = 0; i < k; i++) \{  
        priorityQueue.add(nums\[i\]);  
    \}  
    for (int i = k; i < len; i++) \{  
        // 看一眼  
        Integer topEle = priorityQueue.peek();  
        // 只要当前遍历的元素比堆顶元素大，堆顶出栈，遍历的元素进去  
        if (nums\[i\] > topEle) \{  
            priorityQueue.poll();  
            priorityQueue.add(nums\[i\]);  
        \}  
    \}  
    return priorityQueue.peek();  
\}

}
参考解答3：最小堆更简单的写法。
public class Solution3 {

public int findKthLargest(int\[\] nums, int k) \{  
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));  
    for (int num : nums) \{  
        priorityQueue.add(num);  
        if(priorityQueue.size()==k+1)\{  
            priorityQueue.poll();  
        \}  
    \}  
    return priorityQueue.peek();  
\}