347. 前 K 个高频元素

难度中等653
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

  1. class Solution {
  2. public:
  3.     static bool cmp(const pair<int, int>& p1, const pair<int, int>& p2){
  4.         return p1.second > p2.second;
  5.     }
  6.     // class cmp2{
  7.     // public:
  8.     //     bool operator()(const pair<int, int>& p1, const pair<int, int>& p2){
  9.     //         return p1.second > p2.second;
  10.     //     }
  11.     // };
  12.     vector<int> topKFrequent(vector<int>& nums, int k) {
  13.         unordered_map<int, int> mem;
  14.         vector<int> ans;
  15.         for(auto& c: nums){
  16.             mem[c] ++;
  17.         }
  18.         priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> qs(cmp);
  19.         for(auto& [u, v] : mem){
  20.             if(qs.size() == k){
  21.                 qs.emplace(u, v);
  22.                 qs.pop();
  23.             }else{
  24.                 qs.emplace(u, v);
  25.             }
  26.         }
  27.         while(!qs.empty()){
  28.             ans.push_back(qs.top().first);
  29.             qs.pop();
  30.         }
  31.         return ans;
  32.     }
  33. };

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

难度中等1033
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

  1. class Solution {
  2. public:
  3.     int quick_choose(vector<int>& nums, int l, int r, int k){
  4.         if(l == r){
  5.             return nums[l];
  6.         }
  8.         int i = l - 1, j = r + 1;
  9.         int mid = nums[l];
  10.         while(i < j){
  11.             do i ++; while(nums[i] > mid);
  12.             do j --; while(nums[j] < mid);
  13.             if(i < j) swap(nums[i], nums[j]);
  14.         }
  16.         int dis = j - l + 1;
  17.         if(k <= dis) return quick_choose(nums, l, j, k);
  18.         else return quick_choose(nums, j + 1, r, k - dis);
  19.     }
  20.     int findKthLargest(vector<int>& nums, int k) {
  21.         if(!n) return 0;
  22.         int n = nums.size();
  23.         return quick_choose(nums, 0, n - 1, k);
  24.     }
  25. };