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

发表于 更新于 Disqus：

前几天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
47
#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;
  }
}