LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）】

题目描述：

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

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路一：哈希表记录出现次数，然后用最小堆取，因为每次都是弹出最小的，剩下的一定是K个最大的。

import heapq # 默认是最小堆
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:map_ = {}for i in range(len(nums)):map_[nums[i]] = map_.get(nums[i], 0) + 1pri_que = []for key, freq in map_.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) > k: heapq.heappop(pri_que)result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result

时间复杂度：O(nlogk)
空间复杂度：O(n)

解题思路二：直接排序

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:count = collections.Counter(nums)return [item[0] for item in count.most_common(k)]

时间复杂度：O(nlogn)
空间复杂度：O(n)

解题思路三：堆

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:count = collections.Counter(nums)heap = [(val, key) for key, val in count.items()]return [item[1] for item in heapq.nlargest(k, heap)]

时间复杂度：O(nlogn)
空间复杂度：O(n)

解题思路三：快速排序

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:count = collections.Counter(nums)num_cnt = list(count.items())topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1)return [item[0] for item in topKs]def findTopK(self, num_cnt, k, low, high):pivot = random.randint(low, high)num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]base = num_cnt[low][1]i = lowfor j in range(low + 1, high + 1):if num_cnt[j][1] > base:num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]i += 1num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]if i == k - 1:return num_cnt[:k]elif i > k - 1:return self.findTopK(num_cnt, k, low, i - 1)else:return self.findTopK(num_cnt, k, i + 1, high)

时间复杂度：O(n)
空间复杂度：O(n)