题目描述

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

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

具体见题目详解。

算法思路

这道题很容易想到的是先使用hash_map存储每个元素的出现频次，但是接下来怎么处理就比较麻烦，因为题目要求时间复杂度不高于 $O(N \times LogN)$ ，如果用了传统的排序，那么最低就需要$NLogN$的复杂度。因此需要考虑别的方法，比如桶排序和堆排序，这里我没有采用堆排序一是因为其复杂度其实是$O(N \times LogN)$，其二是因为自己不太会堆排序hhh，桶排序就比较简单了，我们先通过hash表存储每个元素的出现频次，再将key和map倒过来，何谓倒过来？可以这么理解，我们之前的数据结构hash_map[num] = i表示num出现了i次，如果倒过来存储，就变成了counts[i]=num，表示出现了i次的数字包括num，当然，后面需要使用vector进行存储。然后对于新容器键值从高向低遍历，直到统计满k个元素即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash_map;
        for (int i = 0; i < nums.size(); i++) {
            hash_map[nums[i]] ++;
        }
        // 将key和map倒过来
        int maxcounts = nums.size();
        vector< vector<int> > counts(maxcounts + 1);
        // counts[2] = {a, b}表示a, b出现了2次
        for (const auto& it : hash_map) {
            counts[it.second].push_back(it.first);
        }
        vector<int> ans;
        ans.reserve(k);
        for (int i = maxcounts; i > 0 && k > 0; i--) {
            for (const auto& num : counts[i]) {
                ans.push_back(num);
                if (--k == 0) break;
            }
        }
        return ans;
    }
};

时间复杂度为$O(N)$，空间复杂度也是线性$O(N)$