动态规划

数组

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思考

1. 哈希+内置排序

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_dict = defaultdict(int)
        for c in nums:
            num_dict[c]+=1
        index_dict = defaultdict(list)
        for key in num_dict:
            index_dict[num_dict[key]].append(key)
        keys = list(index_dict.keys())
        keys.sort(reverse=True)
        cnt = 0
        res = []
        for key in keys:
            res+=index_dict[key]
            cnt=len(res)
            if cnt == k:
                break
        return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_dict = defaultdict(int)
        for c in nums:
            num_dict[c]+=1
        kvlist = [] 
        for num,freq in num_dict.items():
            kvlist.append((freq,num))
        kvlist.sort(key=lambda x:x[0],reverse=True)    
        res = []
        for item in kvlist[:k]:
            res.append(item[1])
        return res

2. 哈希+最小堆

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_dict = defaultdict(int)
        for c in nums:
            num_dict[c]+=1
        pri_que = [] #小顶堆
        for num,freq in num_dict.items():
            heapq.heappush(pri_que,(freq,num))
            if len(pri_que)>k:
                heapq.heappop(pri_que) 
        res = []
        print(pri_que)
        for item in pri_que:
            res.append(item[1])
        return res