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

Dear 丶 2022-06-07 01:16 124阅读 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;
        }
    };