How can I optimize my solution for large arrays in the Top K Frequent Elements problem?

Using a heap to store the top k frequent elements minimizes sorting overhead, improving performance for large datasets.

Is sorting necessary in the Top K Frequent Elements problem?

No, sorting can be replaced with a heap or bucket sort for improved time complexity in some cases.

What are the time complexities of different approaches for solving the Top K Frequent Elements problem?

Sorting the elements leads to O(N log N) complexity, while using a heap optimizes this to O(N log k). Bucket sort can achieve O(N) in some scenarios.

What data structures are commonly used in solving the Top K Frequent Elements problem?

Hash maps are used for counting frequencies, while heaps and bucket sort are used for efficiently selecting the top k elements.

How does GhostInterview help in solving the Top K Frequent Elements problem?

GhostInterview offers optimized solutions, practical tips on choosing the best approach, and real-time performance feedback to ensure efficient solutions for Top K Frequent Elements.

#347

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。示例 1：输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例 2：输入： nums = [1], k = 1 输出： [1] 示例 3：输入…

数组哈希表分治排序堆（优先队列）

题目描述

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

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

lightbulb

解题思路

方法一：哈希表 + 优先队列（小根堆）

我们可以使用一个哈希表 $\textit{cnt}$ 统计每个元素出现的次数，然后使用一个小根堆（优先队列）来保存前 $k$ 个高频元素。

我们首先遍历一遍数组，统计每个元素出现的次数，然后遍历哈希表，将元素和出现次数存入小根堆中。如果小根堆的大小超过了 $k$ ，我们就将堆顶元素弹出，保证堆的大小始终为 $k$ 。

最后，我们将小根堆中的元素依次弹出，放入结果数组中即可。

时间复杂度 $O(n \times \log k)$ ，空间复杂度 $O(k)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        return [x for x, _ in cnt.most_common(k)]

speed

复杂度分析

指标	值
时间	\mathcal{O}(N)
空间	up to

psychology

面试官常问的追问

外企场景

question_mark
Evaluates the candidate’s understanding of hash maps and sorting algorithms.
question_mark
Assesses how well the candidate can optimize solutions using data structures like heaps.
question_mark
Checks the candidate's ability to apply trade-offs for time and space complexity in algorithm design.

warning

常见陷阱

外企场景

error
Failing to consider the optimization of sorting by using a heap.
error
Incorrectly handling cases where multiple elements have the same frequency.
error
Overlooking edge cases where the array length is small or all elements have the same frequency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the k least frequent elements instead of the most frequent ones.
arrow_right_alt
Modify the problem to allow a dynamic stream of elements instead of a static array.
arrow_right_alt
Return the top k elements but with custom ordering based on an additional condition.

help

常见问题

外企场景

继续练习

#692 前K个高频单词 #451 根据字符出现频率排序 #169 多数元素