个人技术分享

Problem: 347. 前 K 个高频元素

题目描述

思路

1.利用Map集合统计每一个元素的频率（元素作为map集合的键、其频率作为map集合的值）;
2.获取其中出现的最大频率；
3.从最大频率开始，依次将频率最大的前k个添加到结果数组中

复杂度

时间复杂度:

$O(n)$；其中$n$为数组nums的长度

空间复杂度:

$O(1)$

Code

class Solution {
    /**
     * Top K Frequent Elements
     *
     * @param nums Given array
     * @param k    Top k
     * @return int[]
     */
    public int[] topKFrequent(int[] nums, int k) {
        if (nums.length == 1) {
            return new int[]{nums[0]};
        }
        //Calculate the frequent
        Map<Integer, Integer> frequentMap = new HashMap<>();
        for (int num : nums) {
            frequentMap.put(num, frequentMap.getOrDefault(num, 0) + 1);
        }
        //Recode the max times
        int maxTime = 0;
        Set keySet = frequentMap.keySet();
        for (Object key : keySet) {
            maxTime = Math.max(maxTime, frequentMap.get(key));
        }
        int[] res = new int[k];
        while (k > 0) {
            for (Object key : keySet) {
                if (frequentMap.get(key) == maxTime) {
                    res[k - 1] = (Integer) key;
                    k--;
                }
            }
            maxTime--;
        }
        return res;
    }
}