Problem:
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Idea:
Solution 2: Priority queue / max heap
Time complexity: O(n) + O(nlogk)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahuas // Running time: 16 ms class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; for (const int num : nums) ++count[num]; priority_queue<pair<int, int>> q; for (const auto& pair : count) { q.emplace(-pair.second, pair.first); if (q.size() > k) q.pop(); } vector<int> ans; for (int i = 0; i < k; ++i) { ans.push_back(q.top().second); q.pop(); } return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 56 ms class Solution { public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer, Integer> counts = new HashMap<>(); for (int num : nums) counts.put(num, counts.getOrDefault(num, 0) + 1); PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]); for (Integer num : counts.keySet()) { queue.offer(new int[]{counts.get(num), num}); if (queue.size() > k) queue.poll(); } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < k; ++i) ans.add(queue.poll()[1]); return ans; } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 |
""" Author: Huahua Running time: 56 ms """ class Solution: def topKFrequent(self, nums, k): counts = collections.Counter(nums) h = [] for num in counts.keys(): heapq.heappush(h, (counts[num], num)) if len(h) > k: heapq.heappop(h) return [heapq.heappop(h)[1] for i in range(k)] |
Solution 3: Bucket Sort
Time complexity: O(n)
Space complexity: O(n)
C++/hashmap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; int max_freq = 1; for (const int num : nums) max_freq = max(max_freq, ++count[num]); map<int, vector<int>> buckets; for (const auto& kv : count) buckets[kv.second].push_back(kv.first); vector<int> ans; for (int i = max_freq; i >= 1; --i) { auto it = buckets.find(i); if (it == buckets.end()) continue; ans.insert(ans.end(), it->second.begin(), it->second.end()); if (ans.size() == k) return ans; } return ans; } }; |
C++/array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; for (const int num : nums) ++count[num]; vector<vector<int>> buckets(nums.size() + 1); for (const auto& kv : count) buckets[kv.second].push_back(kv.first); vector<int> ans; for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) { const vector<int>& keys = *it; if (keys.empty()) continue; ans.insert(ans.begin(), keys.begin(), keys.end()); if (ans.size() == k) return ans; } return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 23 ms class Solution { public List<Integer> topKFrequent(int[] nums, int k) { List[] buckets = new List[nums.length + 1]; Map<Integer, Integer> counts = new HashMap<>(); for (int num : nums) counts.put(num, counts.getOrDefault(num, 0) + 1); for (int num : counts.keySet()) { int count = counts.get(num); if (buckets[count] == null) buckets[count] = new ArrayList<Integer>(); buckets[count].add(num); } List<Integer> ans = new ArrayList<>(); for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) { if (buckets[i] != null) ans.addAll(buckets[i]); } return ans; } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
""" Author: Huahua Running time: 64 ms """ class Solution: def topKFrequent(self, nums, k): counts = collections.Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num in counts.keys(): buckets[counts[num]].append(num) ans = [] for i in range(len(nums), 0, -1): ans += buckets[i] if len(ans) == k: return ans return ans |