题目：

Given a non-empty array of integers, return the k most frequent elements.

For example,Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

思路：

用map存储元素，key值为元素，value为该元素对应的个数。用vector存储元素及其对应的个数。使用sort对vector进行排序，并重写自定义函数cmp。将前k位的key值存储在最终要返回的数组中。

代码：

bool cmp(const pair<int, int> &x, const pair<int, int> &y) { return x.second > y.second; } class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { map<int, int> m; map<int, int>::iterator it_m; vector<pair<int, int> > v; vector<int> result; for (int i = 0; i < (signed) nums.size(); i++) { m[nums[i]]++; } for (it_m = m.begin(); it_m != m.end(); it_m++) { v.push_back(make_pair(it_m->first, it_m->second)); } sort(v.begin(), v.end(), cmp); for (int i = 0; i < k; i++) { result.push_back(v[i].first); } return result; } };

 

转载于:https://www.cnblogs.com/sindy/p/6933612.html

相关资源：数据结构—成绩单生成器