Array & Hashing
72. 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.
Examples
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 <= 10^5
- -10^4 <= nums[i] <= 10^4
kis in the range [1, number of unique elements in nums]- It is guaranteed that the answer is unique
from typing import Dict, List
k: int = 2 # Number of most frequent elements to find
nums: List[int] = [1, 1, 1, 2, 2, 3]
freq: List[List[int]] = [[] for i in range(len(nums) + 1)]
count: Dict[int, int] = {}
for num in nums:
count[num] = 1 + count.get(num, 0)
# Apply Bucket Sort
for n, c in count.items(): # (1,3), (2,2), (3,1) -> number, frequency
freq[c].append(n) # freq = [[], [3], [2], [1], [], [], []]
res: List[int] = []
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
res.append(n)
if len(res) == k:
print(res)
# <fixed>
# Used count[nums] instead of count[num] (the entire list instead of the loop variable).
# This caused TypeError: unhashable type: 'list'.Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help