本文主要是介绍LeetCode-347. 前 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)
这篇关于LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!