(top200)215. 数组中的第K个最大元素（待总结整理）

(top200)215. 数组中的第K个最大元素（待总结整理） topk问题

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/zi-jie-ti-ku-215-zhong-deng-shu-zu-zhong-kjbd/
剑指offer40

（非递归的）

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        int n=nums.size();
        int le=0, ri=n-1;
        while(true){  
            //快排框架
            int i=le, j=ri;
            int idx = rand() % (ri - le +1) + le;//随机选择pivot
            swap(nums[le], nums[idx]);
            while(i=nums[le]) --j;
                while(in-k) ri=i-1;//将查找范围放在该位置左侧
            else le=i+1;//将查找范围放在该位置右侧
        }
    }
};

作者：gcsxdu
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/215-shu-zu-zhong-de-di-kge-zui-da-yuan-s-vhwd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    int findKthLargest(vector& nums, int k) {
        priority_queue, greater> pq;
        for (auto n : nums) {
            if (pq.size() == k && pq.top() >= n) continue;
            if (pq.size() == k) {
                pq.pop();
            }
            pq.push(n);
        }
        return pq.top();
    }

作者：ikaruga
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/215-by-ikaruga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。