【LeetCode最详尽解答】347. 前K 个高频元素 Top_K_Frequent

【LeetCode最详尽解答】347. 前K 个高频元素 Top_K_Frequent_Elements

本文主要是介绍【LeetCode最详尽解答】347. 前K 个高频元素 Top_K_Frequent_Elements，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

347_前K 个高频元素

直觉

最初，我想统计每个数字的出现次数，并将其存储在字典中，例如 {1: 3, 2: 2, 3: 1}，其中键是元素，值是频率。但是，如何比较这些值呢？我认为应该将其变为 {3: 1, 2: 2, 1: 3}，其中键是频率，值是元素。然而，我卡在了如何对键进行排序的问题上。对键进行排序的时间复杂度是 $\log n)$ ，但问题要求更好的时间复杂度，所以我们应该放弃这种方法。

我看了 Neetcode 的解决方案，但这个问题并不难。例如，给定输入 nums = [1,1,1,2,2,3] 和 k = 2，输出应该是 [1,2]。

首先，直觉是我们需要统计每个数字的频率，然后返回前 k 个最频繁的数字。例如，在这种情况下，会是 {1: 3, 2: 2, 3: 1}。

Neetcode 想出了一个非常巧妙的方法来解决这个问题。它保留了 len(nums) + 1 个位置来存储频率和对应的值。在这种情况下，频率数组会是 [[], [], [], [], [], [], []]，其中 fre[0] 代表出现 0 次的元素，fre[1] 代表出现 1 次的元素，依此类推。然后，我们可以逆序迭代来找到第 k 个最频繁的元素。

为了让频率数组存储我们想要的值，我们可以像这样循环 {1: 3, 2: 2, 3: 1}：

for ele, fre in res.items():freq[fre].append(ele)

更新频率数组后，它看起来像 [[], [3], [2], [1], [], [], []]。然后，我们可以逆序遍历它并将值附加到最终结果数组中。

方法

构建一个哈希表，存储每个数字及其对应的频率值。构建一个频率数组，其中每个索引代表出现的次数，存储在每个索引处的值代表出现该次数的数字。频率数组的长度应为 len(nums) + 1，因为频率范围可能从 0 到 len(nums)，因此总长度为 len(nums) + 1。然后，逆序提取值并将其附加到最终结果数组中。当结果数组的长度等于 k 时，我们可以提前停止循环。

复杂度

时间复杂度：
$O (n)$
- 我们遍历 nums 列表一次以计算每个元素的频率，时间复杂度为 $O (n)$ 。
- 构建频率数组也需要 $O (n)$ 时间，因为我们用每个唯一元素的频率来填充它。
- 最后，我们遍历频率数组以提取前 $k$ 个频繁元素，在最坏情况下，这也需要 $O (n)$ 时间。
空间复杂度：
$O (n)$
- 我们使用一个字典 temp 来存储每个元素的频率，空间复杂度为 $O (n)$ ，其中 $n$ 是唯一元素的数量。
- 我们使用一个列表 freq 来按频率存储元素，最坏情况下，这也需要 $O (n)$ 空间，其中所有元素都是唯一的，每个 freq 列表中最多有一个元素。
- 结果列表 res 将存储前 $k$ 个频繁元素，最坏情况下可以是 $O (k)$ 。然而，由于 $\leq n$ ，这会导致 $O (n)$ 空间复杂度。

代码

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""freq = [[] for i in range(len(nums) + 1)]temp = {}for num in nums:temp[num] = 1 + temp.get(num, 0)for ele, fre in temp.items():freq[fre].append(ele)res = []for i in range(len(freq)-1, -1, -1):for ele in freq[i]:res.append(ele)if len(res) == k:return res