Medium
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]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104kis 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.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# c = Counter(nums)
# a = [key for key, _ in c.most_common(k) ]
# return a
# items = {}
# for num in nums:
# items[num] = items.get(num, 0)+1
# q = sorted(list(items.keys()), key=lambda x: -items[x])
# return q[:k]
# using heap
items = {}
for num in nums:
items[num] = items.get(num, 0)+1
data = [(-v, k) for k, v in items.items()]
heap = data
heapq.heapify(heap)
ans = []
for item in range(k):
x = heapq.heappop(heap)
ans.append(x[1])
return ans