讨论/《哈希表》 - 前 K 个高频元素/
《哈希表》 - 前 K 个高频元素
共 6 个回复
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : nums) { map.put(key, map.getOrDefault(key, 0) + 1); }
        List<int[]> list = new ArrayList<>();
        map.forEach((key, value) -> { list.add(new int[]{key, value}); });
        list.sort(Comparator.comparingInt(a -> a[1]));
        int[] res = new int[k];
        for (int i = 0, j = list.size() - 1; i < k; i++, j--) res[i] = list.get(j)[0];
        return res;
    }
}
2

JavaScript版本~

用哈希表存储每个数字出现的次数,再遍历哈希表存入数组做排序

执行用时:96 ms, 在所有 JavaScript 提交中击败了79.27%的用户

内存消耗:41 MB, 在所有 JavaScript 提交中击败了55.55%的用户

var topKFrequent = function (nums, k) {
    const map = {}, arr = []
    let max = nums[0]
    for (let i = 0; i < nums.length; i++) {
        if (!map[nums[i]]) map[nums[i]] = { val: nums[i], count: 1}
        else map[nums[i]].count += 1
    }
    for (let key in map) {
        arr.push(map[key])
    }
    arr.sort((a, b) => b.count - a.count)   //按出现次数从大到小排序
    arr.length = k  //截断数组长度为k
    return arr.map(item => item.val)
};
1
class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        nums.reduce(into: [:]) {
            $0[$1, default: 0] += 1
        }.sorted { $0.value  > $1.value }.prefix(k).map { $0.key }
    }
}
1

t显然为O(n)

简洁方法:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        unordered_map<int,int> mp; //first为键 second为值
        vector<int> ans;
        for(int i=0;i<nums.size();i++)//遍历nums 记录次数
        {
            mp[nums[i]]++;
        }
        int max=0;
        for(auto i:mp)//遍历哈希表 寻找最大次数
        {
            if(i.second>max) max=i.second;
        }
        while(k>0)
        {
            for(auto i:mp)//遍历
            {
                if(i.second==max)//如果找到就加入向量 
                {
                    ans.push_back(i.first);k--;
                }
            }
            max--;//最大值减小
        }
        return ans;
    }
};

这个题的优先队列第一次接触,尤其是格式,priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp);