Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/347.html
347. Top K Frequent Elements
Level
Medium
Description
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
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.
Solution
To obtain an algorithm with time complexity better than O(*n* log *n*)
, use maps. This solution has time complexity O(*n* log *k*)
.
Use two maps
to store each number and its count and store each count and the numbers that have the count, respectively.
- The first map is a hash map
- the second map is a tree map
Loop over nums
to obtain each number and its count, and store the numbers and the counts in the first map. Then loop over the entries of the first map to obtain each cound and the numbers that have the count, and store the counts and the numbers in the second map. Initialize the second map such that keys are sorted in descending order. Then loop over the second map to obtain the k most frequent elements.
Pitfall
Clarify on: what if there is a tie?
Code
-
import java.util.*; public class Top_K_Frequent_Elements { // ref: https://leetcode.com/problems/top-k-frequent-elements/solution/ class Solution_official_oN { int[] unique; Map<Integer, Integer> count; public void swap(int a, int b) { int tmp = unique[a]; unique[a] = unique[b]; unique[b] = tmp; } public int partition(int left, int right, int pivot_index) { int pivot_frequency = count.get(unique[pivot_index]); // 1. move pivot to end swap(pivot_index, right); int store_index = left; // 2. move all less frequent elements to the left for (int i = left; i <= right; i++) { if (count.get(unique[i]) < pivot_frequency) { swap(store_index, i); store_index++; } } // 3. move pivot to its final place swap(store_index, right); return store_index; } public void quickselect(int left, int right, int k_smallest) { /* Sort a list within left..right till kth less frequent element takes its place. */ // base case: the list contains only one element if (left == right) return; // select a random pivot_index Random random_num = new Random(); int pivot_index = left + random_num.nextInt(right - left); // find the pivot position in a sorted list pivot_index = partition(left, right, pivot_index); // if the pivot is in its final sorted position if (k_smallest == pivot_index) { return; } else if (k_smallest < pivot_index) { // go left quickselect(left, pivot_index - 1, k_smallest); } else { // go right quickselect(pivot_index + 1, right, k_smallest); } } public int[] topKFrequent(int[] nums, int k) { // build hash map : character and how often it appears count = new HashMap<>(); for (int num: nums) { count.put(num, count.getOrDefault(num, 0) + 1); } // array of unique elements int n = count.size(); unique = new int[n]; int i = 0; for (int num: count.keySet()) { unique[i] = num; i++; } // kth top frequent element is (n - k)th less frequent. // Do a partial sort: from less frequent to the most frequent, till // (n - k)th less frequent element takes its place (n - k) in a sorted array. // All element on the left are less frequent. // All the elements on the right are more frequent. quickselect(0, n - 1, n - k); // Return top k frequent elements return Arrays.copyOfRange(unique, n - k, n); } } class Solution_optimize { public int[] topKFrequent(int[] nums, int k) { // O(1) time if (k == nums.length) { return nums; } // 1. build hash map : character and how often it appears // O(N) time Map<Integer, Integer> countMap = new HashMap(); for (int n: nums) { countMap.put(n, countMap.getOrDefault(n, 0) + 1); } // init heap 'the less frequent element first', poll到最后剩下K个最大的 Queue<Integer> heap = new PriorityQueue<>( (n1, n2) -> countMap.get(n1) - countMap.get(n2)); // 2. keep k top frequent elements in the heap // O(N log k) < O(N log N) time for (int n: countMap.keySet()) { heap.add(n); if (heap.size() > k) heap.poll(); } // 3. build an output array // O(k log k) time int[] top = new int[k]; for(int i = k - 1; i >= 0; --i) { top[i] = heap.poll(); } return top; } } // use an array to save numbers into different bucket whose index is the frequency public class Solution_bucketCount { public List<Integer> topKFrequent(int[] nums, int k) { List<Integer> result = new LinkedList<>(); if (nums == null || nums.length == 0) { return result; } Map<Integer, Integer> hm = new HashMap<>(); for(int n: nums){ hm.put(n, hm.getOrDefault(n, 0) + 1); } // @note: corner case: if there is only one number in nums, we need the bucket has index 1. LinkedList[] bucket = new LinkedList[nums.length + 1]; for(int n: hm.keySet()){ int freq = hm.get(n); if(bucket[freq] == null) { bucket[freq] = new LinkedList<>(); } bucket[freq].add(n); } for(int i = bucket.length - 1; i > 0 && k > 0; i--){ // @note: possible tie happening if(bucket[i] != null){ List<Integer> list = bucket[i]; result.addAll(list); k-= list.size(); } } return result; } } class Solution { public List<Integer> topKFrequent(int[] nums, int k) { List<Integer> result = new ArrayList<>(); if (nums == null || nums.length == 0) { return result; } // from num, to its count HashMap<Integer, Integer> hm = new HashMap<>(); // to store top k PriorityQueue<Pair> heap = new PriorityQueue<>( (o1, o2) -> (o1.count - o2.count) ); for (int each: nums) { hm.put(each, 1 + hm.getOrDefault(each, 0)); } for (Map.Entry<Integer, Integer> entry: hm.entrySet()) { heap.offer(new Pair(entry.getKey(), entry.getValue())); // @note: i missed it if (heap.size() > k) { heap.poll(); } } while (!heap.isEmpty()) { result.add(heap.poll().num); } Collections.reverse(result); return result; } } class Pair{ int num; int count; public Pair(int num, int count){ this.num=num; this.count=count; } } } ############ class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Long> frequency = Arrays.stream(nums).boxed().collect( Collectors.groupingBy(Function.identity(), Collectors.counting())); Queue<Map.Entry<Integer, Long>> queue = new PriorityQueue<>(Map.Entry.comparingByValue()); for (var entry : frequency.entrySet()) { queue.offer(entry); if (queue.size() > k) { queue.poll(); } } return queue.stream().mapToInt(Map.Entry::getKey).toArray(); } }
-
// OJ: https://leetcode.com/problems/top-k-frequent-elements/ // Time: O(N + U) on average, O(N + U^2) in the worst case // Space: O(U) class Solution { public: vector<int> topKFrequent(vector<int>& A, int k) { if (A.size() == k) return A; unordered_map<int, int> cnt; for (int n : A) cnt[n]++; vector<int> ans; for (auto &[n, c] : cnt) ans.push_back(n); if (ans.size() == k) return ans; auto partition = [&](int L, int R) { int i = L, j = L, pivotIndex = L + rand() % (R - L + 1), pivot = cnt[ans[pivotIndex]]; swap(ans[pivotIndex], ans[R]); for (; i < R; ++i) { if (cnt[ans[i]] > pivot) swap(ans[i], ans[j++]); } swap(ans[j], ans[R]); return j; }; auto quickSelect = [&](int k) { int L = 0, R = ans.size() - 1; while (L < R) { int M = partition(L, R); if (M + 1 == k) break; if (M + 1 > k) R = M - 1; else L = M + 1; } }; quickSelect(k); ans.resize(k); return ans; } };
-
from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # Count the frequency of each element in the list cnt = Counter(nums) # Sort the elements by frequency in decreasing order # diff from below solution: sorted(cnt), not sorted(cnt.items()) # more in https://leetcode.ca/2017-10-22-692-Top-K-Frequent-Words/ sorted_freqs = sorted(cnt, key=lambda x: (-cnt[x], x)) return sorted_freqs[:k] class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # Count the frequency of each element in the list freqs = Counter(nums) # Sort the elements by frequency in decreasing order sorted_freqs = sorted(freqs.items(), key=lambda x: x[1], reverse=True) # also passing OJ: sorted_freqs = sorted(freqs.items(), key=lambda x: -x[1]) # Take the top k elements top_k = [num for num, freq in sorted_freqs[:k]] return top_k ''' >>> from heapq import heappush >>> h = [] >>> heappush(h, (3,1)) >>> heappush(h, (1,1)) >>> heappush(h, (2,1)) >>> h [(1, 1), (3, 1), (2, 1)] >>> from heapq import heappop >>> heappop(h) (1, 1) >>> heappop(h) (2, 1) >>> heappop(h) (3, 1) ''' from collections import Counter class Solution: # heap def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = Counter(nums) hp = [] for num, freq in cnt.items(): heappush(hp, (freq, num)) if len(hp) > k: heappop(hp) return [v[1] for v in hp] from typing import List import random # O(n log(n)) in the average case # O(n^2) worst case class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: freq_map = {} for num in nums: freq_map[num] = freq_map.get(num, 0) + 1 freq_list = list(freq_map.items()) self.quick_select(freq_list, 0, len(freq_list) - 1, k) return [num for num, freq in freq_list[:k]] def quick_select(self, freq_list, start, end, k): if start == end: return pivot_idx = random.randint(start, end) pivot_freq = freq_list[pivot_idx][1] left = start right = end while left <= right: while freq_list[left][1] > pivot_freq: left += 1 while freq_list[right][1] < pivot_freq: right -= 1 if left <= right: freq_list[left], freq_list[right] = freq_list[right], freq_list[left] left += 1 right -= 1 if k <= right: self.quick_select(freq_list, start, right, k) elif k >= left: self.quick_select(freq_list, left, end, k) ########### ''' >>> x = [1, 2, 3] >>> x.append([4, 5]) >>> print(x) [1, 2, 3, [4, 5]] >>> x = [1, 2, 3] >>> x.extend([4, 5]) >>> print(x) [1, 2, 3, 4, 5] ''' class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: freq = Counter(nums) # not always filled, max possible frequency is len(nums) [1,1,1,1,...] buckets = [[] for _ in range(len(nums) + 1)] for num, freq in freq.items(): buckets[freq].append(num) res = [] for bucket in reversed(buckets): if bucket: res.extend(bucket) if len(res) >= k: break return res[:k] ############ class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ d = {} res = [] ans = [] buckets = [[] for _ in range(len(nums) + 1)] for num in nums: d[num] = d.get(num, 0) + 1 for key in d: res.append((d[key], key)) for t in res: freq, key = t buckets[freq].append(key) buckets.reverse() for item in buckets: if item and k > 0: while item and k > 0: ans.append(item.pop()) k -= 1 if k == 0: return ans return ans
-
func topKFrequent(nums []int, k int) []int { cnt := map[int]int{} for _, v := range nums { cnt[v]++ } h := hp{} for v, freq := range cnt { heap.Push(&h, pair{v, freq}) if len(h) > k { heap.Pop(&h) } } ans := make([]int, k) for i := range ans { ans[i] = heap.Pop(&h).(pair).v } return ans } type pair struct{ v, cnt int } type hp []pair func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i].cnt < h[j].cnt } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) } func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
-
function topKFrequent(nums: number[], k: number): number[] { let hashMap = new Map(); for (let num of nums) { hashMap.set(num, (hashMap.get(num) || 0) + 1); } let list = [...hashMap]; list.sort((a, b) => b[1] - a[1]); let ans = []; for (let i = 0; i < k; i++) { ans.push(list[i][0]); } return ans; }
-
use std::collections::HashMap; impl Solution { pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> { let mut map = HashMap::new(); let mut max_count = 0; for &num in nums.iter() { let val = map.get(&num).unwrap_or(&0) + 1; map.insert(num, val); max_count = max_count.max(val); } let mut k = k as usize; let mut res = vec![0; k]; while k > 0 { let mut next = 0; for key in map.keys() { let val = map[key]; if val == max_count { res[k - 1] = *key; k -= 1; } else if val < max_count { next = next.max(val); } } max_count = next; } res } }