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) + 1
pri_que = []
for key, freq in map_.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k:
heapq.heappop(pri_que)
result = [0] * k
for 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 = low
for 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 += 1
num_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)