LeetCode刷题（130）～前 K 个高频元素【最小堆｜快速排列 难点！】

题目描述

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

示例 1:

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

  

 

  
1
  
2
 

示例 2:

输入: nums = [1], k = 1
输出: [1]

  

 

  
1
  
2
 

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

解答 By 海轰

提交代码

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> m; for(int num:nums) ++m[num]; vector<int> a; for(auto i:m) a.push_back(i.second); sort(a.begin(),a.end()); vector<int> b; for(int i=a.size()-1;i>=(a.size()-k)&&i>=0;--i) { b.push_back(a[i]); } sort(b.begin(),b.end()); vector<int> ans; for(auto i:m) { if(i.second>=b[0]) ans.push_back(i.first); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

运行结果

解答

Demo（最小堆）

 static bool cmp(pair<int, int>& m, pair<int, int>& n) { return m.second > n.second; } vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> occurrences; for (auto& v : nums) { occurrences[v]++; } // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数 priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp); for (auto& [num, count] : occurrences) { if (q.size() == k) { if (q.top().second < count) { q.pop(); q.emplace(num, count); } } else { q.emplace(num, count); } } vector<int> ret; while (!q.empty()) { ret.emplace_back(q.top().first); q.pop(); } return ret; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

运行结果

Demo（快速排列）

void qsort(vector<pair<int, int>>& v, int start, int end, vector<int>& ret, int k) { int picked = rand() % (end - start + 1) + start; swap(v[picked], v[start]); int pivot = v[start].second; int index = start; for (int i = start + 1; i <= end; i++) { if (v[i].second >= pivot) { swap(v[index + 1], v[i]); index++; } } swap(v[start], v[index]); if (k <= index - start) { qsort(v, start, index - 1, ret, k); } else { for (int i = start; i <= index; i++) { ret.push_back(v[i].first); } if (k > index - start + 1) { qsort(v, index + 1, end, ret, k - (index - start + 1)); } } } vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> occurrences; for (auto& v: nums) { occurrences[v]++; } vector<pair<int, int>> values; for (auto& kv: occurrences) { values.push_back(kv); } vector<int> ret; qsort(values, 0, values.size() - 1, ret, k); return ret; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108444660