力扣链接

题意

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

• 1
• -104 

思路及解答

堆排序

这道题就是经典的 topK 问题， 实现一个小根堆，规定堆的元素大小是 k 个，将比堆顶大的元素进堆。最后遍历完数组之后，此时堆顶是 k 个元素中最小的，有就是所有元素中第 k 大的了。

可以用PriorityQueue的最小堆来实现：

public class KthLargestMinHeap {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue minHeap = new PriorityQueue(k);
        
        for (int num : nums) {
            if (minHeap.size()  minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        return minHeap.peek();
    }
}

升序排序后索引为 len - k 的元素

其实题目已经告诉我们了：

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

因此，升序排序以后，返回索引为 len - k 这个元素即可。

代码如下：

public class Solution {
 
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len - k];
    }
}

• 时间复杂度：O(NlogN)。这里 N 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为O(NlogN)。
• 空间复杂度：O(1)。这里是原地排序，没有借助额外的辅助空间。

但是，如果出了这道题，显然不是想让你调 API ，而是看你对快排的理解

借助快排 partition 操作定位（推荐）

“快速排序” 中的 partition(切分)操作简单介绍如下：

• 对于某个索引i，nums[i] 已经排序完，即 nums[i] 经过 partition(切分)操作以后会放置在它 “最终应该放置的地方”；
• nums[left] 到 nums[i - 1] 中的所有元素都不大于 nums[i]；
• nums[i + 1] 到 nums[right] 中的所有元素都不小于 nums[i]。

很显然，nums[i] 最终所在的位置，也就是它排序后的具体位置。也就是说，如果实现的排序是降序排序，那么第k个位置的数据，也确定就是第k大的

而这样每经过一次 partition操作就能缩小搜索的范围，这样的思想叫做 “减而治之”(是 “分而治之” 思想的特例)。下面是参考代码：

public class Solution {
 
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
 
        // 转换一下，第 k 大元素的索引是 len - k
        int target = len - k;
 
        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index 

• 时间复杂度：O(N)。这里 N 是数组的长度。
• 空间复杂度：O(1)。切分过程可以不借助额外的数组空间，仅通过交换数组元素实现，没有借助额外的辅助空间。

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top