leetcode 347. Top K Frequent Elements 使用HashMap计数-蒲公英云

leetcode 347. Top K Frequent Elements 使用HashMap计数

Dear 丶 2022-06-07 01:16 245阅读 0赞

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;
    }
};