找出数组中的第K大的数或者第K小的数

本是古典 何须时尚 2022-12-31 01:25 294阅读 0赞 
  1. class Solution
  2. { 
  3. public:
  4.     int findKthLargest(vector<int>& res, int k)
  5.     { 
  6.         priority_queue<int, vector<int>, greater<int>> smallHeap;
  7.         for (auto& i : res) { 
  8.             if (smallHeap.size() < k)
  9.             { 
  10.                 smallHeap.push(i);
  11.             }
  12.             else { 
  13.                 if (smallHeap.top() < i)
  14.                 { 
  15.                     smallHeap.pop();
  16.                     smallHeap.push(i);
  17.                 }
  18.             }
  19.         }
  20.         return smallHeap.top();
  22.     }
  23. };

此处需要用到priority_queue，要熟悉该函数的语法。可以选择排序方式，是从大到小还是从小到大排序。当方式按照从小到大排序时，也就greater，top函数返回的是K个里面的最小值。

  1. priority_queue<int, vector<int>, greater<int> >jp;
  2.     jp.push(10);
  3.     jp.push(1);
  4.     jp.push(2);
  5.     cout << jp.top() << endl;
  6.     输出：1

发表评论

表情：
评论列表 （有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数组中第K大的数

    题目描述 有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存

    迈不过友情╰迈不过友情╰/ 0 赞/ 288 阅读

    相关 求一个数组中第k大的数方法

    求一个数组中第k大的数，我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn),n为数组长度。但是我们都知道快速排

    忘是亡心i忘是亡心i/ 0 赞/ 370 阅读

    相关 寻找第K大的数

    1，对于一个有序数组 则为第K个数，O（1） 2，对于一个无序数组 使用修改的快排划分算法，时间复杂度为O（n） 3，对于两个无序数组

    小咪咪小咪咪/ 0 赞/ 289 阅读