堆

我以为是啥呢

结果是一种树???

插眼…

小顶堆

priority_queue<int, vector<int>, greater<int>> pq;

大顶堆

priority_queue<int> pq;

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

第一种想法:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

时间复杂度$O(n \log n)$

空间复杂度$O(1)$(忽略sort的栈)

解法2:

小顶堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;

        for(int x : nums) {
            pq.push(x);
            if(pq.size() > k) {
                pq.pop();
            }
        }
        return pq.top();
    }
};

时间复杂度$O(n \log k)$

空间复杂度$O(k)$

解法3:

分治 + 快排

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;
        return quickSelect(nums, 0, nums.size() - 1, target);
    }

    int quickSelect(vector<int>& nums, int l, int r, int target) {
        int pivot = nums[l];
        int i = l, j = r;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            nums[j] = nums[i];
        }
        
        nums[i] = pivot;

        if (i == target)
            return nums[i];
        if (i < target)
            return quickSelect(nums, i + 1, r, target);
        return quickSelect(nums, l, i - 1, target);
    }
};

期望时间复杂度为$O(n)$

但是我直接超时了

哈哈哈哈哈

原来最坏情况是$O(n^2)$

被测试数据拿捏了…