Leetcode|堆|快排|215. 数组中的第K个最大元素

class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int i = left, j = right;
        int pivot = rand() % (right - left + 1) + left;
        swap(nums[left], nums[pivot]);
        int pos = nums[left];
        while (i < j) {
            while (nums[j] >= pos && i < j) j--;
            while (nums[i] <= pos && i < j) i++;
            if (i < j) swap(nums[i], nums[j]);
        }
        swap(nums[left], nums[i]);
        return i;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        int targetidx = size - k;   // 第k大元素在升序数组中的索引
        int left = 0, right = size - 1;
        while (true) {
            int pivot = partition(nums, left, right);
            if (pivot == targetidx) 
                return nums[pivot];
            else if (pivot < targetidx)
                left = pivot + 1;
            else if (pivot > targetidx)
                right = pivot - 1;
        }
        return -1;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto& val : nums) 
            if (q.size() == k && q.top() < val) {
                q.pop();
                q.emplace(val);
            } else if (q.size() < k)
                q.emplace(val);
        return q.top();
    }
};

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