【力扣二刷思路】DAY3

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

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

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

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

思路

1. findKthLargest 函数：公共接口函数，接收一个整数数组 nums 和一个整数 k 作为参数，返回第 k 大的元素。在该函数中，直接调用了私有成员函数 qucikSelect，并将结果返回。

2. qucikSelect 函数：递归接收一个整数数组 nums 和一个整数 k 作为参数，返回数组中第 k 大的元素。该函数的实现采用了快速选择算法的思想。

   • 在每次调用中，随机选择数组中的一个元素 p 作为 pivot（中轴）。
   • 然后将数组 nums 中小于、等于和大于 pivot 的元素分别放入三个数组 small、equal 和 big 中。
   • 如果 k 小于等于 big 的大小，则在 big 数组中继续递归查找第 k 大的元素。
   • 如果 k 大于 big 的大小但小于等于 nums 减去 small 的大小，说明第 k 大的元素位于 equal 中，直接返回 pivot。
   • 如果 k 大于 nums 减去 small 的大小，则在 small 数组中继续递归查找第 k 减去 small 大小的元素。

3. 递归结束条件：递归结束条件是当数组大小等于 1 时，直接返回数组中唯一的元素。

4. 时间复杂度：平均时间复杂度为 O(n)，最坏情况下为 O(n^2)，其中 n 为数组的大小。这是因为快速选择算法的平均情况下每次能够将搜索范围缩小为原来的一半，但最坏情况下可能需要遍历整个数组。

5. 空间复杂度：除了递归调用栈外，额外使用了三个辅助数组，因此空间复杂度为 O(n)。

题解

class Solution {
public:
    // 主函数，找出无序数组中第 k 大的元素
    int findKthLargest(vector<int>& nums, int k) {
        // 调用快速选择算法并返回结果
        return quickSelect(nums, k);
    }

private:
    // 快速选择算法
    int quickSelect(vector<int>& nums, int k) {
        // 随机选择一个元素作为 pivot（中轴）
        int pivot = nums[rand() % nums.size()];
        // 定义三个辅助数组，分别存放小于、等于和大于 pivot 的元素
        vector<int> smaller, equal, bigger;
        // 遍历数组，将元素根据大小放入不同的辅助数组中
        for (int num : nums) {
            if (num < pivot)
                smaller.push_back(num);
            else if (num == pivot)
                equal.push_back(num);
            else
                bigger.push_back(num);
        }
        // 如果 k 小于等于大于 pivot 的元素数量，则在 bigger 数组中继续查找第 k 大的元素
        if (k <= bigger.size())
            return quickSelect(bigger, k);
        // 如果 k 大于 bigger 的大小但小于等于 nums 减去 smaller 的大小，则返回 pivot
        if (k <= bigger.size() + equal.size())
            return pivot;
        // 否则，在 smaller 数组中继续查找第 k - (bigger.size() + equal.size()) 大的元素
        return quickSelect(smaller, k - bigger.size() - equal.size());
    }
};

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
35