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.
My code:
import collections
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
record_dict=collections.defaultdict()
for item in nums:
if item not in record_dict:
record_dict[item]=1
else:
record_dict[item]+=1
map_dict=collections.defaultdict(list)
for item in record_dict.keys():
map_dict[record_dict[item]].append(item)
result=list(map_dict.keys())
result.sort()
result=result[::-1]#dec order
i=0
choose=0
record=[]
while i<k:
value=result[choose]
tmp_map=map_dict[value]
for item in tmp_map:
record.append(item)
i+=1
choose+=1
record=record[:k]
return record
Solution: https://leetcode.com/problems/top-k-frequent-elements/