leetcode 347. Top K Frequent Elements 使用HashMap计数
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.
这道题很简单,直接使用HashMap计数,然后排序即可。
代码如下:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
class Solution
{
public List<Integer> topKFrequent(int[] nums, int k)
{
List<Integer> res=new ArrayList<Integer>();
if(nums==null || nums.length<=0 || k<=0 || k>=nums.length+1)
return res;
Map<Integer, Integer> map=new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++)
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Entry<Integer, Integer> a,Entry<Integer, Integer> b) {
return b.getValue()-a.getValue();
} });
for(int i=0;i<k;i++)
res.add(list.get(i).getKey());
return res;
}
}
下面是C++的做法,直接统计计数即可
代码如下:
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.second >= b.second;
}
class Solution
{
public:
vector<int> topKFrequent(vector<int>& nums, int k)
{
map<int, int> mmp;
for (int i : nums)
mmp[i]++;
vector<pair<int, int>> all;
for (auto i : mmp)
all.push_back({ i.first,i.second });
sort(all.begin(), all.end(), cmp);
vector<int> res;
for (int i = 0; i < k; i++)
res.push_back(all[i].first);
return res;
}
};
还没有评论,来说两句吧...