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

求第k个最大的元素，
从大到小排序，取第k个数，即为第k个最大的元素。

暴力

先按从大到小排序，时间复杂度O(nlogn), 返回 nums[k-1]。

快速选择

快速选择算法，递归

时间O(n), 空间O(logn)：因为有递归栈空间O(logn)

class Solution {
public:
    int quick_select(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]; // x 建议选 nums[l + r >> 1]
        while (i < j)
        {
            do i++; while (nums[i] > x); // 左边均是 >= x的，从大到小排序
            do j--; while (nums[j] < x); // 右边均是 <= x的，但是代码里要写成 < x;
            if (i < j) swap(nums[i], nums[j]);
        }

        int sl = j - l + 1;
        // 递归一侧
        if (k <= sl) return quick_select(nums, l, j, k);
        else return quick_select(nums, j + 1, r, k - sl);
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quick_select(nums, 0, nums.size()-1, k);
    }
};

快速选择算法，非递归（优化空间）

去掉递归栈空间，用while循环
时间O(n), 空间O(1), 空间复杂度最优解

class Solution {
public:
    int quick_select(vector<int>& nums, int l, int r, int k)
    {
        // 用while循环
        while (true)
        {
            if (l >= r) return nums[l];

            int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // x 建议选 nums[l + r >> 1]
            while (i < j)
            {
                do i++; while (nums[i] > x); // 左边均是 >= x的，从大到小排序
                do j--; while (nums[j] < x); // 右边均是 <= x的，但是代码里要写成 < x;
                if (i < j) swap(nums[i], nums[j]);
            }

            int sl = j - l + 1;
            if (k <= sl) 
                r = j; // 更新参数r
            else 
                // 实测，先更新k要快些
                k = k - sl, l = j + 1; // 先更新k再更新l，因为k用到了原来的l，不过我这里用sl保存了，按理说先更新l也可以
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quick_select(nums, 0, nums.size()-1, k);
    }
};

堆排序

最小堆：时间O(nlogk), 空间O(k)

使用STL建立小根堆：
priority_queue<int, vector<int>, greater<int>> Q;

建立大根堆：
priority_queue<int> Qmin;

堆使用于什么题目和情况下呢？
关键字：第k个。和第k个相关，就可以尝试用堆。
维护动态数据的最大和最小值，可以考虑堆。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 小根堆，顶部元素是最小值，保持堆内只有k个元素，这样堆顶元素就是第k个最大的元素
        priority_queue<int, vector<int>, greater<int>> Q;

        for (int i = 0; i < nums.size(); i++)
        {
            // 如果堆中元素数量 Q.size() < k个，就把当前的元素加入堆中
            if (Q.size() < k) 
                Q.push(nums[i]);
            else if (Q.top() < nums[i])// 如果堆顶元素 < 当前元素nums[i]，就更新堆顶
            {
                Q.pop(); // 弹出堆顶元素
                Q.push(nums[i]); // 新元素入堆，替换堆顶
            }
        }
        // 返回堆顶元素，即为第k个最大的元素
        return Q.top();
    }
};

总结

快速选择和堆算法的适用场景

• 快速选择只适用于 确定数量的情况下，即数组的数量是固定的，静态不变的。
• 如果是动态情况，数组数量不是确定的，就只能用堆的方法。堆的方法也有小根堆和大根堆可以选择，小根堆的时间复杂度较优，