509，数组中的第K个最大元素

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

The old dreams were good dreams. They didn’t work out, but I’m glad I had them.

曾经的梦都是美梦，虽未成真，但庆幸我曾拥有过。

问题描述

在未排序的数组中找到第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 ≤ 数组的长度。

先排序再查找

这题是让找出排序后的第k个最大的元素，所以最简单的一种方式就是先对数组进行排序，然后再查找。关于排序，我公众号之前介绍了有十几种排序算法，具体可以在公众号的目录中查看。代码比较简单，我们来看一下

1public int findKthLargest(int[] nums, int k) {
2    Arrays.sort(nums);//先排序
3    return nums[nums.length - k];//在查找
4}

使用最小堆

这题只让找出最大的第k个元素即可，没说一定要对数组进行排序，所以我们还可以使用最小堆来解决。解决方式就是一个个遍历原数组的值，添加到堆中，添加之后如果堆中元素个数大于k的时候，我们就把最顶端的元素给移除掉，因为是最小堆，所以移除的就是堆中最小的值。

 1public int findKthLargest(int[] nums, int k) {
 2    final PriorityQueue<Integer> queue = new PriorityQueue<>();
 3    for (int val : nums) {
 4        queue.add(val);//加入堆中
 5        //如果堆中元素大于k，则把堆顶元素给移除
 6        if (queue.size() > k)
 7            queue.poll();
 8    }
 9    return queue.peek();//返回堆顶元素
10}

参考快速排序

快速排序是先选择一个中枢（一般我们选第一个），然后遍历后面的元素，最终会把数组分为两部分，前面部分比中枢值小，后面部分大于或等于中枢值。

分开之后中枢值所在的位置如果从后面数是第k个，我们直接返回中枢值即可。
如果从后面数大于k，说明要找的值还在后面这部分，我们只需按照同样的方式从后面部分开始找即可。
如果从后面数小于k，说明要找的值在前面部分，我们同样从前面部分开始查找。

原理比较简单，我们来看下代码

 1public int findKthLargest(int[] nums, int k) {
 2    k = nums.length - k;//注意这里的k已经变了
 3    int lo = 0, hi = nums.length - 1;
 4    while (lo <= hi) {
 5        int i = lo;
 6        //这里把数组以A[lo]的大小分为两部分，
 7        //一部分是小于A[lo]的，一部分是大于A[lo]的
 8        // [lo,i]<A[lo]，[i+1,j)>=A[lo]
 9        for (int j = lo + 1; j <= hi; j++)
10            if (nums[j] < nums[lo])
11                swap(nums, j, ++i);
12        swap(nums, lo, i);
13        if (k == i)
14            return nums[i];
15        else if (k < i)
16            hi = i - 1;
17        else
18            lo = i + 1;
19    }
20    return -1;
21}
22
23//交换两个元素的值
24private void swap(int[] nums, int i, int j) {
25    if (i != j) {
26        nums[i] ^= nums[j];
27        nums[j] ^= nums[i];
28        nums[i] ^= nums[j];
29    }
30}