美文网首页
[leetcode] 215. Kth Largest Elem

[leetcode] 215. Kth Largest Elem

作者: Kevifunau | 来源:发表于2018-10-03 12:08 被阅读0次

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

找出无序数组中第K大个数 -->( 有序情况下 , index =k-1 的值)

这里我采用 快选的方法
时间复杂度 O(n) 空间复杂度O(1)

class Solution {
public:
   int findKthLargest(vector<int>& nums, int k) {
       // 第K大 index 为 k-1 
       quickselect(nums,0,nums.size()-1,k-1);
       return nums[k-1];
   }
private:
   void quickselect(vector<int>& nums, int l, int r,int k){
       // 快排 l..j > nums[l]  
       // i..r < nums[l]
       int j = l;
       for(int i = l+1; i <= r; i++ ){
           if(nums[i] > nums[l]){
               j++;
               swap(nums[i],nums[j]);
           }
       }
       swap(nums[l],nums[j]);
       // nums[l..j] >= nums[l] >= nums[i..r] 

       //快选
       if(j >k) quickselect(nums,l,j,k);
       else if (j <k) quickselect(nums,j+1,r,k);
       //招到某次 j == k 
       else return;
   }
   
};
image.png

当然 也可以用堆排序 需要额外开O(k)的空间 时间复杂度O(NlogK)
c++ 中 priority_queue 默认是 最大堆

image.png
#include <queue>
using namespace std;
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 求第K大个元素 --> 一个 大小为K的 小顶堆的 堆顶
        priority_queue<int, vector<int>, greater<int> > minp;
        //把数组所有元素都往 最小堆里塞 同时维护 最小堆大小为K
        for(auto i:nums){
            minp.push(i);
            if(minp.size() > k){
                minp.pop();
            }
        }
        return minp.top();
      
    }
};
image.png

相关文章

网友评论

      本文标题:[leetcode] 215. Kth Largest Elem

      本文链接:https://www.haomeiwen.com/subject/leuzoftx.html