leetcode 347 Top K Freq Elments

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]

347. Top K Frequent Elements

题目要求：Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

第一遍自己写的O(n log n),只能说时间复杂度小于等于O(nlogn),不太满足题意的样子

1. 用dic 记录每个数字出现的次数

2. sorted()按照出现的次数大小进行排序

3. 返回前k个

   class Solution:
       def topKFrequent(self, nums: List[int], k: int) -> List[int]:
           dic={}
           count=0
           for i in range(len(nums)):
               if nums[i] not in dic:
                   dic[nums[i]]=count
               else:
                   dic[nums[i]]+=1
                   
           a=sorted(dic.items(),key=lambda x: x[1],reverse=True)
           #[(1,3),(2,2),(3,1)]
           
           return [x[0] for x in a[:k]]

List Comprehensions：

https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions

List time-complexity

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Pop last	O(1)	O(1)
Pop intermediate	O(k)	O(k)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)