心之所向便是光

Leetcode 215.数组中的第K个最大元素

  • 2021-07-23
  • 作者 Ender
  • 3.95K 字
  • 次阅读

题目描述：

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

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

示例 1:

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

示例 2:

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

提示：

  • $1 <= k <= nums.length <= 10^4$
  • $-10^4 <= nums[i] <= 10^4$

链接：

https://leetcode-cn.com/problems/kth-largest-element-in-an-array

题目分析

1.快速排序改进

  这道题就是非常经典的 Top-K 问题。当然最简单的方法就是直接将整个数组进行排序后再返回第 K 个数。但是这样的处理方法做了很多没有用的功课，比如我们其实只需要获取第 K 大的数，而比它大的那些数和比它小的那些数是无需进行排序的。我们可以想到快速排序的原理，就是每一次选取一个哨兵节点并且将比它大的和比它小的数放到它的两边。那么我们只需要这样做，并且根据放置后的结果选择大的那些数还是小的那些数进行同样的操作，直到最后划分的哨兵刚好分出来 K-1 个比它大的数就可以。
  具体的操作是这样的：我们使用一个 quicksort 函数对 [begin, end] 区间进行排序，哨兵结点就是 nums[begin]，将这个区间划分为大于 nums[begin] 和小于 nums[begin] 两边后，返回 nums[begin] 最后的下标。然后我们根据返回的这个下标判断需要对左边的区间还是右边的区间进行新一轮的选择。如此迭代直到最后找到第 k 个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int quicksort(vector<int>& nums, int begin, int end){
        int temp = nums[begin];
        while(begin < end){
            while(begin < end && temp > nums[end]){
                end--;
            }
            nums[begin] = nums[end];
            while(begin < end && temp <= nums[begin]){
                begin++;
            }
            nums[end] = nums[begin];
        }
        nums[begin] = temp;
        return begin;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int flag = quicksort(nums, 0, nums.size()-1);
        int begin = 0, end = nums.size()-1;
        while(flag != k-1){
            if(flag > k-1){
                end = flag - 1;
            }
            else{
                begin = flag + 1;
            }
            flag = quicksort(nums, begin, end);
        }
        return nums[flag];
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组中元素的个数。我们每次划分都相当于对该区间进行了一次遍历。假设每次刚好划分出一半的数组，则我们需要划分的数组分别为 $n、n/2、n/4…$，他们的和趋近于 $2n$，因此平均时间复杂度是 $O(n)$ 的。但是最坏的情况下，我们每一次划分都只分出一个元素，则每次划分的数组分别为 $n、n-1、n-2…$，他们的和是 $O(n^2)$ 的。
  空间复杂度：$O(1)$。我们都在原数组上进行操作，也没有使用到递归函数，所需要的空间是常数级的。

2.堆

  上面的方法有什么缺点呢？一个是不稳定，受数组划分的影响比较大。另外一个缺点与实际应用相关，如果需要进行处理的数组非常大，没有办法一次性加载到内存中，或者是经常需要添加新元素（例如某个游戏的积分 Top 100 榜），上面的方法是一次性的，没有办法进行处理。这个时候，我们就可以使用堆的做法。
  我们维护一个大小为 K 的最小堆，则堆顶就是这个堆中第 K 大的元素。之后我们遍历数组，不断将遍历到的数字与堆顶进行比较，如果比堆顶大则置换掉堆顶，并且重新调整堆使得堆顶仍然为堆里最小的元素。遍历整个数组后堆顶就是这个数组中第 K 大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    void adjustMinHeap(vector<int>& nums, int begin, int k){
        while(2 * begin + 1 < k){
            int minChild = 2 * begin + 1; // 赋为左孩子
            // 若右孩子更小则赋为右孩子
            if(minChild + 1 < k && nums[minChild] > nums[minChild + 1]){
                minChild = minChild + 1;
            }
            // 孩子比双亲小则交换
            if(nums[begin] > nums[minChild]){
                swap(nums[begin], nums[minChild]);
                // 需要重新调整被破坏的孩子
                begin = minChild;
            }
            else break;
        }
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 建立小顶堆（大小为 K）
        for(int begin = k / 2 - 1; begin >= 0; begin--){
            adjustMinHeap(nums, begin, k);
        }
        // 遍历后面的数组
        for(int i = k; i < nums.size(); i++){
            // 将大于堆顶的数与堆顶交换，并调整堆
            if(nums[i] > nums[0]){
                swap(nums[0], nums[i]);
                adjustMinHeap(nums, 0, k);
            }
        }
        return nums[0];
    }
};

  时间复杂度：$O(n\log k)$，其中 $n、k$ 分别是数组的大小和题目中的 K。对于一个已经建立好的堆，置换堆顶元素后只需要从上往下调整需要交换的那条分支，因此时间复杂度为 $O(\log k)$，并且是稳定的。我们在建堆之后只需要遍历数组，如果置换则需要调整堆，因此时间复杂度为 $O(n\log k)$。而建堆的时间复杂度为 $O(k)$（根据调和级数的积分公式得出）。因为 $k\leq n$，总的时间复杂度为 $O(n\log k)$。（在实际应用中 K 的值一般不会很大，因此当 $n$ 很大的时候时间复杂度是近似于 $O(n)$ 的，并且比较稳定。）
  空间复杂度：$O(1)$。我们的最小堆直接建立在了原数组中。如果原数组不能改动的话则另外需要 $O(k)$ 的空间保存堆。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,
最后编辑：2021-08-03