LeetCode215. 数组中的第K个最大元素（2024冬季每日一题 17）

给定整数数组 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<=k<=nums.length<=10^5$
$-10^4<=nums[i]<=10^4$

思路一：

• 通过快排变形，求出第 n - k - 1 小的数字
• 求第 k 大的数 = 求第 n - k -1 小的数

时间复杂度：$O(logN)$

class Solution {
public:
    int quick_sort(vector<int>& nums, int l, int r, int k){
        if(l >= r) return nums[l];
        int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
        while(i < j){
            while(nums[++i] < x);
            while(nums[--j] > x);
            if(i < j) swap(nums[i], nums[j]);
        }
        if(k <= j - l + 1) return quick_sort(nums, l, j, k);
        else return quick_sort(nums, j + 1, r, k - (j - l + 1));
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quick_sort(nums, 0, n - 1, n - k + 1);
    }
};

思路二：

• 通过构建大根堆，求出第 k 大的数
• 构建大根堆是堆排序的一部分，相当于通过堆排序，求出第 k 大的数

时间复杂度：$O(NlogN)$

class Solution {
public:
    int n = 0;
    int findKthLargest(vector<int>& nums, int k) {
        n = nums.size();
        for(int i = n / 2; i >= 0; i--) down(nums, i);
        while(--k){
            nums[0] = nums[n - 1];
            n--;
            down(nums, 0);
        }
        return nums[0];
    }
    void down(vector<int>&v, int u){
        int t = u;
        if(u * 2 < n && v[u * 2] > v[t]) t = u * 2;
        if(u * 2 + 1 < n && v[u * 2 + 1] > v[t]) t = u * 2 + 1;
        if(u != t){
            swap(v[t], v[u]);
            down(v, t);
        }
    }
};