题目:
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
解题思路:
要返回出现频率前k高的元素,那么我们首先肯定要知道每个元素出现的次数,我们可以借助Map来实现。
有了所有元素的出现次数,我们只需要知道出现的最高次数maxCnt,然后创建一个长度为maxCnt+1的数组buckets用来存储出现次数相同的元素。buckets[i]表示出现次数为i的所有元素。
最后倒序遍历bucket,输出前k个元素即可。
class Solution {public int[] topKFrequent(int[] nums, int k) {// 1、用Map统计每个元素出现的次数Map<Integer, Integer> cntMap = new HashMap<>();for(int num : nums){cntMap.merge(num, 1, (oldVal, newVal) -> oldVal + newVal);}// 2、计算最大的出现次数int maxCnt = Collections.max(cntMap.values());// 3、定义长度为maxCnt+1的list数组,每个数组元素用来存放出现次数相同的元素集合List<Integer>[] buckets = new ArrayList[maxCnt+1];Arrays.setAll(buckets, i -> new ArrayList<>());for(Map.Entry<Integer, Integer> e : cntMap.entrySet()){buckets[e.getValue()].add(e.getKey());}// 4、倒序遍历buckets,把出现次数前k大的元素加入答案int[] ans = new int[k];int j = 0;for(int i = maxCnt; i >= 0 && j < k; i--){for(int x : buckets[i]){ans[j++] = x;}}return ans;}
}