347. Top K Frequent Elements
## description
## 347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2
Output: [1,2]
Constraints:
- –1 <= nums.length <= 105
- –-104 <= nums[i] <= 104
- –k is in the range [1, the number of unique elements in the array].
- –It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
## notes
### Intuition
Bucket sort by frequency. Since the maximum frequency is n, we can use an array where index represents frequency and values are the elements with that frequency. Scanning from highest to lowest frequency gives us the top k elements.
### Implementation
First, count frequencies with a hashmap. Then create a frequency array of length n + 1 (indices 0 to n), where each index is a list of elements with that frequency. Iterate backward through this array, collecting elements until we have k items.
### Edge-cases
Multiple elements can share the same frequency, so each bucket is a list. When collecting results, iterate through all elements in each bucket before moving to the next lower frequency.
- –Time: O(n) — frequency counting and bucket iteration
- –Space: O(n) — hashmap and frequency buckets
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
5 map = {}
6 for num in nums:
7 if num in map:
8 map[num] += 1
9 else:
10 map[num] = 1
11
12 freq_table = [[] for _ in range(len(nums) + 1)]
13 for num in map:
14 freq = map[num]
15 freq_table[freq].append(num)
16
17 ans = []
18 for i in range(len(freq_table) - 1, -1, -1):
19 for j in range(len(freq_table[i]) - 1, -1, -1):
20 ans.append(freq_table[i][j])
21 if len(ans) == k:
22 return ans
23
24
25 return ans
26
27
28
29if __name__ == "__main__":
30 # Include one-off tests here or debugging logic that can be run by running this file
31 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
32 solution = Solution()
33