无标题文章
2016-05-18 本文已影响0人
lulupango
347. Top K Frequent Elements
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].
解析:
很明显本题应该用到的是hashtable和heap等相关的数据结果,可选的有unordered_map用来统计array
里面每个元素出现的次数,接着依照次数进行排序得到topK个元素,可选的有优先队列、最小堆等,
也可以直接将map转换为vector,然后对vector进行排序。转换如下:
vector<pair<int, int>> pv(begin(my_map), end(my_map))
实现部分如下:
方法1:使用了priority_queue
struct node
{
int x, y;
friend bool operator < (node a, node b)
{
return a.y < b.y; //结构体中,x的优先级高
}
node(int xx,int yy) {
x = xx;
y = yy;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map <int,int> times;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (times.count(nums[i]) > 0) times[nums[i]]++;
else times[nums[i]] = 1;
}
priority_queue<node> pq;
for (auto it = times.begin(); it != times.end(); it++) {
struct node n1 = node(it->first,it->second);
pq.push(n1);
}
for(int i = 0 ;i < k; i++) {
res.push_back(pq.top().x);
pq.pop();
}
return res;
}
方法2:使用stl自带的函数nth_element是将前n个元素排序,同时除了第n个元素位置正确外其他的均不变
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> my_map;
for_each (begin(nums), end(nums), [&my_map](int i){ my_map[i]++;});
vector<pair<int, int>> pv(begin(my_map), end(my_map));
nth_element(begin(pv), begin(pv)+k, end(pv), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
vector<int> result;
transform(begin(pv), begin(pv)+k,back_inserter(result), [](pair<int, int> a){return a.first;});
return result;
}
方法3:直接对vector进行排序
map<int,int> myMap;
struct CmpByValue {
bool operator()(const pair<int,int>& l, const pair<int,int>& r)
{
return l.second > r.second;
}
}; //this Compair construct is used to sort the pair by pair.second().
vector<int> topKFrequent(vector<int>& nums, int k) {
for(auto i=nums.begin();i!=nums.end();i++) {
if(myMap.find(*i)!=myMap.end()) {
myMap[*i]++;
} else {
myMap[*i]=1;
}
}
vector<pair<int,int>> name_score_vec(myMap.begin(), myMap.end());
//排序 vector<int> vec;
sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
for(int j=0;j<k;j++) {
vec.push_back(name_score_vec[j].first);
}
return vec;
}