剑指 Offer II 060. 出现频率最高的 k 个数字

---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20060.%20%E5%87%BA%E7%8E%B0%E9%A2%91%E7%8E%87%E6%9C%80%E9%AB%98%E7%9A%84%20k%20%E4%B8%AA%E6%95%B0%E5%AD%97/README.md

  剑指 Offer II 060. 出现频率最高的 k 个数字

标题描述

  给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 恣意序次 返答复案。
 
示例 1:

1. <strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2
2. <strong>输出: </strong>[1,2]

复制代码

示例 2:

1. <strong>输入: </strong>nums = [1], k = 1
2. <strong>输出: </strong>[1]

复制代码

 
提示：

• 1 <= nums.length <= 105
  
• k 的取值范围是 [1, 数组中不相同的元素的个数]
  
• 标题数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
  

 
进阶：所设盘算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 
注意：本题与主站 347 题相同：https://leetcode.cn/problems/top-k-frequent-elements/
  解法

  方法一：哈希表 + 优先队列（小根堆）

利用哈希表统计每个元素出现的次数，然后利用优先队列（小根堆）维护前                                         k                                  k                     k 个出现次数最多的元素。
时间复杂度                                    O                         (                         n                         log                         ⁡                         k                         )                              O(n\log k)                  O(nlogk)。
  Python3

1. class Solution:
2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3.         cnt = Counter(nums)
4.         return [v[0] for v in cnt.most_common(k)]

复制代码

Java

1. class Solution {
2.     public int[] topKFrequent(int[] nums, int k) {
3.         Map<Integer, Long> frequency = Arrays.stream(nums).boxed().collect(
4.             Collectors.groupingBy(Function.identity(), Collectors.counting()));
5.         Queue<Map.Entry<Integer, Long>> queue = new PriorityQueue<>(Map.Entry.comparingByValue());
6.         for (var entry : frequency.entrySet()) {
7.             queue.offer(entry);
8.             if (queue.size() > k) {
9.                 queue.poll();
10.             }
11.         }
12.         return queue.stream().mapToInt(Map.Entry::getKey).toArray();
13.     }
14. }

复制代码

C++

1. using pii = pair<int, int>;
3. class Solution {
4. public:
5.     vector<int> topKFrequent(vector<int>& nums, int k) {
6.         unordered_map<int, int> cnt;
7.         for (int v : nums) ++cnt[v];
8.         priority_queue<pii, vector<pii>, greater<pii>> pq;
9.         for (auto& [num, freq] : cnt) {
10.             pq.push({freq, num});
11.             if (pq.size() > k) {
12.                 pq.pop();
13.             }
14.         }
15.         vector<int> ans(k);
16.         for (int i = 0; i < k; ++i) {
17.             ans[i] = pq.top().second;
18.             pq.pop();
19.         }
20.         return ans;
21.     }
22. };

复制代码

Go

1. func topKFrequent(nums []int, k int) []int {
2.         cnt := map[int]int{}
3.         for _, v := range nums {
4.                 cnt[v]++
5.         }
6.         h := hp{}
7.         for v, freq := range cnt {
8.                 heap.Push(&h, pair{v, freq})
9.                 if len(h) > k {
10.                         heap.Pop(&h)
11.                 }
12.         }
13.         ans := make([]int, k)
14.         for i := range ans {
15.                 ans[i] = heap.Pop(&h).(pair).v
16.         }
17.         return ans
18. }
20. type pair struct{ v, cnt int }
21. type hp []pair
23. func (h hp) Len() int           { return len(h) }
24. func (h hp) Less(i, j int) bool { return h[i].cnt < h[j].cnt }
25. func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
26. func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
27. func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

复制代码

TypeScript

1. function topKFrequent(nums: number[], k: number): number[] {
2.     let hashMap = new Map();
3.     for (let num of nums) {
4.         hashMap.set(num, (hashMap.get(num) || 0) + 1);
5.     }
6.     let list = [...hashMap];
7.     list.sort((a, b) => b[1] - a[1]);
8.     let ans = [];
9.     for (let i = 0; i < k; i++) {
10.         ans.push(list[i][0]);
11.     }
12.     return ans;
13. }

复制代码

Rust

1. use std::collections::HashMap;
2. impl Solution {
3.     pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
4.         let mut map = HashMap::new();
5.         let mut max_count = 0;
6.         for &num in nums.iter() {
7.             let val = map.get(&num).unwrap_or(&0) + 1;
8.             map.insert(num, val);
9.             max_count = max_count.max(val);
10.         }
11.         let mut k = k as usize;
12.         let mut res = vec![0; k];
13.         while k > 0 {
14.             let mut next = 0;
15.             for key in map.keys() {
16.                 let val = map[key];
17.                 if val == max_count {
18.                     res[k - 1] = *key;
19.                     k -= 1;
20.                 } else if val < max_count {
21.                     next = next.max(val);
22.                 }
23.             }
24.             max_count = next;
25.         }
26.         res
27.     }
28. }

复制代码

Swift

1. import HeapModule
3. class Solution {
4.     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
5.         var frequency: [Int: Int] = [:]
6.         for num in nums {
7.             frequency[num, default: 0] += 1
8.         }
10.         var freqHeap = Heap<FreqElement>()
11.         for (key, value) in frequency {
12.             freqHeap.insert(.init(val: key, freq: value))
13.             if freqHeap.count > k {
14.                 freqHeap.removeMin()
15.             }
16.         }
17.         var ans = [Int]()
18.         while let element = freqHeap.popMax() {
19.             ans.append(element.val)
20.         }
21.         return ans
22.     }
23. }
25. struct FreqElement: Comparable {
26.     let val: Int
27.     let freq: Int
29.     static func < (lhs: FreqElement, rhs: FreqElement) -> Bool {
30.         lhs.freq < rhs.freq
31.     }
33.     static func == (lhs: FreqElement, rhs: FreqElement) -> Bool {
34.         lhs.freq == rhs.freq
35.     }
36. }

复制代码

   方法二

  Python3

1. class Solution:
2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3.         cnt = Counter(nums)
4.         hp = []
5.         for num, freq in cnt.items():
6.             heappush(hp, (freq, num))
7.             if len(hp) > k:
8.                 heappop(hp)
9.         return [v[1] for v in hp]

复制代码

Java

1. class Solution {
2.     public int[] topKFrequent(int[] nums, int k) {
3.         Map<Integer, Integer> cnt = new HashMap<>();
4.         for (int v : nums) {
5.             cnt.put(v, cnt.getOrDefault(v, 0) + 1);
6.         }
7.         PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
8.         for (var e : cnt.entrySet()) {
9.             pq.offer(new int[] {e.getKey(), e.getValue()});
10.             if (pq.size() > k) {
11.                 pq.poll();
12.             }
13.         }
14.         int[] ans = new int[k];
15.         for (int i = 0; i < k; ++i) {
16.             ans[i] = pq.poll()[0];
17.         }
18.         return ans;
19.     }
20. }

复制代码

TypeScript

1. function topKFrequent(nums: number[], k: number): number[] {
2.     const map = new Map<number, number>();
3.     let maxCount = 0;
4.     for (const num of nums) {
5.         map.set(num, (map.get(num) ?? 0) + 1);
6.         maxCount = Math.max(maxCount, map.get(num));
7.     }
9.     const res = [];
10.     while (k > 0) {
11.         for (const key of map.keys()) {
12.             if (map.get(key) === maxCount) {
13.                 res.push(key);
14.                 k--;
15.             }
16.         }
17.         maxCount--;
18.     }
19.     return res;
20. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。