网站制作软件都是什么,深圳建设银行网站首页,做网站后台有前途吗,创建网址快捷方式LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆#xff08;优先队列#xff09;】 题目描述#xff1a;解题思路一#xff1a;哈希表记录出现次数#xff0c;然后用最小堆取#xff0c;因为每次都是弹出最小的#xff0c;剩下的一定是K… LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆优先队列】 题目描述解题思路一哈希表记录出现次数然后用最小堆取因为每次都是弹出最小的剩下的一定是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 105 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)
