本文主要是介绍347. Top K Frequent Elements(Leetcode每日一题-2020.09.07)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem
Given a non-empty array of integers, return the k most frequent elements.
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.
- It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
- You can return the answer in any order.
Example1
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example2
Input: nums = [1], k = 1
Output: [1]
Solution
map+multimap(Multimaps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order, and where multiple elements can have equivalent keys.)
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {map<int,int> num2cnt;multimap<int,int> cnt2num;for(auto &num:nums){++num2cnt[num];}for(auto it = num2cnt.begin();it != num2cnt.end();++it){cnt2num.insert ( std::pair<int,int>(it->second,it->first) );}vector<int> ret;for(auto rit = cnt2num.crbegin(); rit != cnt2num.crend() && k;++rit,--k){ret.push_back(rit->second);}return ret;}
};
这篇关于347. Top K Frequent Elements(Leetcode每日一题-2020.09.07)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
