top_k_frequent_elements
1from collections import Counter 2 3 4# @leet start 5class Solution: 6 def topKFrequent(self, nums: list[int], k: int) -> list[int]: 7 """ 8 To find the top k most frequent elements, one way is to sort the elements 9 in $O(n{}log{}n)$ time to have all the items next to each other. 10 Then, we would do a groupby, so we could have a key -> value pair of 11 item to frequency. Finally, we could sort that groupby again in descending 12 order and then return that. 13 14 However, there's a faster way using a heap. We can find the frequency of 15 each item by using a hashmap in $O(n)$ time, and then popping off the most 16 common ones in $O(log{}n)$ time, and doing that $k$ times for a complexity 17 of $O(n{}log{}k)$ time. 18 19 There is a better way that involves grouping using a hashmap and then quickselecting 20 in $O(n)$ time but I didn't do that for this question. 21 """ 22 c = Counter(nums) 23 24 return [x[0] for x in c.most_common(k)] 25 26 27# @leet end 28sol = Solution() 29 30 31def test(): 32 assert sol.topKFrequent([1, 1, 1, 2, 2, 3], 2) == [1, 2] 33 assert sol.topKFrequent([1], 1) == [1]
class
Solution:
6class Solution: 7 def topKFrequent(self, nums: list[int], k: int) -> list[int]: 8 """ 9 To find the top k most frequent elements, one way is to sort the elements 10 in $O(n{}log{}n)$ time to have all the items next to each other. 11 Then, we would do a groupby, so we could have a key -> value pair of 12 item to frequency. Finally, we could sort that groupby again in descending 13 order and then return that. 14 15 However, there's a faster way using a heap. We can find the frequency of 16 each item by using a hashmap in $O(n)$ time, and then popping off the most 17 common ones in $O(log{}n)$ time, and doing that $k$ times for a complexity 18 of $O(n{}log{}k)$ time. 19 20 There is a better way that involves grouping using a hashmap and then quickselecting 21 in $O(n)$ time but I didn't do that for this question. 22 """ 23 c = Counter(nums) 24 25 return [x[0] for x in c.most_common(k)]
def
topKFrequent(self, nums: list[int], k: int) -> list[int]:
7 def topKFrequent(self, nums: list[int], k: int) -> list[int]: 8 """ 9 To find the top k most frequent elements, one way is to sort the elements 10 in $O(n{}log{}n)$ time to have all the items next to each other. 11 Then, we would do a groupby, so we could have a key -> value pair of 12 item to frequency. Finally, we could sort that groupby again in descending 13 order and then return that. 14 15 However, there's a faster way using a heap. We can find the frequency of 16 each item by using a hashmap in $O(n)$ time, and then popping off the most 17 common ones in $O(log{}n)$ time, and doing that $k$ times for a complexity 18 of $O(n{}log{}k)$ time. 19 20 There is a better way that involves grouping using a hashmap and then quickselecting 21 in $O(n)$ time but I didn't do that for this question. 22 """ 23 c = Counter(nums) 24 25 return [x[0] for x in c.most_common(k)]
To find the top k most frequent elements, one way is to sort the elements in $O(n{}log{}n)$ time to have all the items next to each other. Then, we would do a groupby, so we could have a key -> value pair of item to frequency. Finally, we could sort that groupby again in descending order and then return that.
However, there's a faster way using a heap. We can find the frequency of each item by using a hashmap in $O(n)$ time, and then popping off the most common ones in $O(log{}n)$ time, and doing that $k$ times for a complexity of $O(n{}log{}k)$ time.
There is a better way that involves grouping using a hashmap and then quickselecting in $O(n)$ time but I didn't do that for this question.
sol =
<Solution object>
def
test():