"""
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]
"""
"""
用dict实现的木桶排序
解法一：木桶+sort
解法二：木桶+heap(堆)
解法三：维护一个n-k的最大堆((有局限性,如果是第k大,会出问题))。此题是前k大的都append里面了
"""
class Solution1:
def topKFrequent(self, nums, k):
count_list = dict()
res = []
for num in nums:
count_list[num] = count_list.get(num, 0) + 1
#如果count_list[num]没有value,则value是0,否则是value+1
#dict.get(key, default=None)
#key -- 字典中要查找的键。
#default -- 如果指定键的值不存在时，返回该默认值。
t = sorted(count_list.items(), key=lambda l: l[1], reverse=True)
#sorted(iterable, key=None, reverse=False) 返回的是一个list
#iterable -- 可迭代对象
#key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可 #迭代对象中的一个元素来进行排序。
#lambda 输入l是(key,value),输出l[1]是value. 可以理解l[0]是key
#reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
for i in range(k):
res.append(t[i][0]) # t[i][0]表示第i个tuple的第1个元素,t[i][1]则表示第二个元素
return res """
解法二：木桶+heap
python heap
nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
heapq.heappush(heap, num) # 第一种加入堆
heapq.heapify(nums) #第二种生成堆
print([heapq.heappop(heap) for _ in range(len(nums))]) # 堆排序结果
nums = [1, 3, 4, 5, 2]
print(heapq.nlargest(3, nums)) [5, 4, 3]
print(heapq.nsmallest(3, nums)) [1, 2, 3]
"""
class Solution2:
def topKFrequent(self, nums, k):
import heapq
count_list = dict()
for num in nums:
count_list[num] = count_list.get(num, 0) + 1
p = list() #存储堆排序后的结果
for i in count_list.items():
heapq.heappush(p, (i[1], i[0])) #加入堆，每个结点是个tuple(,)
return [i[1] for i in heapq.nlargest(k, p)] #这里的i[1] 其实是上一行的i[0]
"""
堆默认root是最小值
解法三：维护一个n-k的最大堆(有局限性,最大的值最后入堆,会出问题)
最大堆需要将最小堆的值取反
"""
class Solution3:
def topKFrequent(self, nums, k):
import heapq
count_list = dict()
for num in nums:
count_list[num] = count_list.get(num, 0) + 1
p = list()
res = list()
for i in count_list.items():
heapq.heappush(p, (-i[1], -i[0])) #bug前面没写heapq
if len(p) > len(count_list) - k:
_, val = heapq.heappop(p) #bug前面没写heapq
res.append(-val)
return res