Medium

题目描述

给你一个整数数组 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^5
  • -10^4 <= nums[i] <= 10^4
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

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

解题思路

这道题有多种解法，我们来分析几种主要方法：

方法一：哈希表 + 最小堆（推荐）

首先统计每个元素的出现频率，然后使用大小为 k 的最小堆来维护前 k 个高频元素。当堆的大小超过 k 时，移除堆顶元素（频率最小的）。最后堆中剩下的就是前 k 个高频元素。

方法二：桶排序

统计频率后，使用桶排序的思想。创建一个数组，索引代表频率，值存储该频率对应的元素列表。由于最大频率不会超过数组长度，所以从后往前遍历桶，取出前 k 个元素即可。

方法三：快速选择

基于快速排序的分治思想，可以在平均 O(n) 时间内找到第 k 大的元素。先统计频率，然后对频率进行快速选择。

最小堆方法实现简单且稳定，时间复杂度 O(n log k)，当 k 较小时性能很好，是最常用的解法。

代码实现

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        for (auto& p : count) {
            pq.push({p.second, p.first});
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        vector<int> result;
        while (!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        
        return result;
    }
};

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        from collections import Counter
        
        count = Counter(nums)
        
        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)
        
        return [num for freq, num in heap]

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        var pq = new SortedSet<(int freq, int num)>();
        
        foreach (var kvp in count) {
            pq.Add((kvp.Value, kvp.Key));
            if (pq.Count > k) {
                pq.Remove(pq.Min);
            }
        }
        
        return pq.Select(x => x.num).ToArray();
    }
}

var topKFrequent = function(nums, k) {
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const heap = [];
    
    for (const [num, freq] of count) {
        heap.push([freq, num]);
        if (heap.length > k) {
            heap.sort((a, b) => a[0] - b[0]);
            heap.shift();
        }
    }
    
    return heap.map(item => item[1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
最小堆O(n log k)O(n + k)
桶排序O(n)O(n)
快速选择O(n) 平均，O(n²) 最坏O(n)

其中 n 为数组长度，k 为要求的元素个数。推荐使用最小堆方法，在 k 较小时效率很高且实现简单。

相关题目