前K个高频元素

Leetcode Link: 347. 前 K 个高频元素 - 力扣（LeetCode）

题目

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

解法一

思路：利用优先队列或者最大堆即可完成，但是在此之前我们需要先统计每个数字的个数

题解：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from queue import PriorityQueue
        # 统计
        count = Counter(nums)
        # 送入优先队列
        q = PriorityQueue()
        for key, val in count.items():
            q.put((-val, key))
        # 取出前k个
        res = []
        for _ in range(k):
            cur = q.get()
            res.append(cur[1])
        
        return res

解法二

思路：直接用Counter的自带函数完成

题解：

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)]

知识点

记 c = Counter(lst)

c.most_common(n): 返回一个列表，其中包含 n 个最常见的元素(0索引)及出现次数(1索引)，按常见程度由高到低排序。返回的这个列表每个元素是个tuple

c.total(): 计算计数总和

c.elements(): 返回一个迭代器，其中每个元素将重复出现计数值所指定次。元素会按首次出现的顺序返回。

解法三

思路：堆排序, 小根堆。

题解：

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)]

知识点

python 中只有小根堆。

堆是一个二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。

因此，把堆看作原生的 Python list 也没什么奇怪的： heap[0] 表示最小的元素

创建一个堆：使用 list 来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个 list 转换成堆

heapq.heapify(x): 将list x 转换成堆，原地，线性时间内。

heapq.heappush(heap, item) : 将 item 的值加入 heap 中，保持堆的不变性。

heapq.heappop(heap) : 弹出并返回 heap 的最小的元素，保持堆的不变性。使用 heap[0] ，可以只访问最小的元素而不弹出它。

heap.heappushpop(heap. item) : 将 item 放入堆中，然后弹出并返回 heap 的最小元素，速度更快

heapq.nlargest(n, iterable, key=None) : 从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: sorted(iterable, key=key, reverse=True)[:n]。

heapq.nsmallest(n, iterable, key=None): 从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: sorted(iterable, key=key)[:n]。

解法四

思路

利用快速排序(没理解，看着好像还行，就先抄过来了。)

记录每个数字出现的次数对每个数及对应次数通过快排进行排序，返回前k个快排步骤

随机选一个中间值作为基准，并把它挪到最左侧
从第2个元素开始遍历，遍历过程中，要把比基准大的挪到左边，比基准小的挪到右边
i 指向比基准大的元素，只要 j 指向的元素比基准小，就把 j 位置的元素和 i 后面一个位置的元素对调。并且 i 后移一位，这样 i 指向的元素以及 i 之前的元素都是比基准大的元素（基准本身除外）
j 遍历到末尾后，此时 i 指向的就是排序后的列表中比基准大的最后一个元素，将该元素和基准对调，即 num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]。这样排序后的列表就是在 i 位置前的都比 i 大，i 位置后的都比 i 小

接下来就是分治部分了

如果 i == k - 1，也就是 i 及之前的元素恰好组成了我们想要的 topK，直接返回前 k 个元素
如果 i > k - 1, 也就是 i 及之前的元素组成了 top (K+N)，要对前 i 个元素再进行一次快排，从 top (K+N) 里选出 topK: findTopK(num_cnt, k, low, i - 1)
如果 i < k - 1，也就是 i 及之前的元素组成了 top (K-N)，要对 i 之后的元素再进行快排，在之后的元素中选出 topN: findTopK(num_cnt, k, i + 1, high)

返回快排结果中的数字部分

题解

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)

My Obsidian Blog

探索

前K个高频元素

题目

解法一

解法二

解法三

解法四

启发和联系

关系图谱

目录