数组中出现次数最多的K个数

前几天Google onsite面试,已挂。今天仔细思考了面试中一道没写出来的题,发现也并不难。诶,只能怪当时脑抽了。

题目大意

给定一个巨大的无序数组,输出数组中出现次数最多的K个数。

比如:(为了方便看,暂且排了序)

1,1,1,2,2,3,4,5,6,7,7,7,8,8,8,8

输出:

8,7,1

输出顺序无关紧要。但是我这里用堆,很容易就可以输出有序的。

解决方法

Step 1. 用哈希表统计出各个元素出现次数 - count()

Step 2. 用容量为K的最小堆找出最大的K个数 - topK()

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <exception>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
struct comparer {
bool operator() (const pair<int, int> &a, const pair<int, int> &b) {
return a.second > b.second;
}
};
public:
vector<int> topK(unordered_map<int, int> &input, int k) {
if (input.size() < k)
throw exception("Illeagle Parameters");
priority_queue<pair<int, int>, vector<pair<int, int>>, comparer> heap;
auto iter = input.begin();
for (int i = 0; i < k; i++, iter++) {
heap.push(*iter);
}
for (; iter != input.end(); iter++) {
if (iter->second > heap.top().second) {
heap.pop();
heap.push(*iter);
}
}
vector<int> result;
while (!heap.empty()) {
result.push_back(heap.top().first);
heap.pop();
}
reverse(result.begin(), result.end()); // not necessary
return result;
}

unordered_map<int, int> count(vector<int>& input) {
unordered_map<int, int> statistics;
for (int value : input) {
statistics[value]++;
}
return statistics;
}
};

测试

1
2
3
4
5
6
7
8
9
10
11
int test[] = {1,1,1,2,2,3,4,5,6,7,7,7,8,8,8,8};

int main() {
Solution sol;
vector<int> input(&test[0], &test[sizeof(test) / sizeof(int) - 1]);
auto stat = sol.count(input);
vector<int> result = sol.topK(stat, 3);
for (int value : result) {
cout << value << endl;
}
}