时间复杂度：\(O(n\log{k})\)，其中 \(n\) 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 \(O(n)\) 的；接着，遍历用于存储元素频率的 map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这一系列操作的时间复杂度是 \(O(n\log{k})\) 的；最后，弹出堆中的元素所需的时间复杂度是 \(O(k\log{k})\) 的。因此，总的时间复杂度是 \(O(n\log{k})\) 的。
空间复杂度：\(O(n)\)，最坏情况下（每个元素都不同），map 需要存储 \(n\) 个键值对，优先队列需要存储 \(k\) 个元素，因此，空间复杂度是 \(O(n)\) 的。
解法三：桶排序（bucket sort） 思路最后，为了进一步优化时间复杂度，可以采用桶排序（bucket sort），即用空间复杂度换取时间复杂度。
第一步和解法二相同，也是统计出数组中元素的频次。接着，将数组中的元素按照出现频次进行分组，即出现频次为 \(i\) 的元素存放在第 \(i\) 个桶。最后，从桶中逆序取出前 \(k\) 个元素。
Java 实现 class Solution { public List<Integer> topKFrequent(int[] nums, int k) { // 统计元素的频次 Map<Integer, Integer> int2FreqMap = new HashMap<>(16); for (int num : nums) { int2FreqMap.put(num, int2FreqMap.getOrDefault(num, 0) + 1); } // 桶排序 List<Integer>[] bucket = new List[nums.length + 1]; for (Integer key : int2FreqMap.keySet()) { int freq = int2FreqMap.get(key); if (bucket[freq] == null) { bucket[freq] = new ArrayList<>(); } bucket[freq].add(key); } // 逆序（频次由高到低）取出元素 List<Integer> ret = new ArrayList<>(); for (int i = nums.length; i >= 0 && ret.size() < k; --i) { if (bucket[i] != null) { ret.addAll(bucket[i]); } } return ret; } } Python 实现 class Solution: def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ # 统计元素的频率 freq_dict = dict() for num in nums: freq_dict[num] = freq_dict.get(num, 0) + 1 # 桶排序 bucket = [[] for _ in range(len(nums) + 1)] for key, value in freq_dict.items(): bucket[value].append(key) # 逆序取出前k个元素 ret = list() for i in range(len(nums), -1, -1): if bucket[i]: ret.extend(bucket[i]) if len(ret) >= k: break return ret[:k] 复杂度分析时间复杂度：\(O(n)\)，其中 \(n\) 表示数组的长度。
空间复杂度：\(O(n)\)