【原】LeetCode 347.前K个高频元素

题目描述:

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2：

输入: nums = [1], k = 1

输出: [1]

提示：

1. 1 <= nums.length <= 10⁵

2.k 的取值范围是 [1, 数组中不相同的元素的个数]

3.题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：

你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

题目分析:

用桶排序求解。首先创建字典集map，统计数组中的每个元素出现的次数，元素为键，出现的次数为值。然后创建list集合，遍历map，按照元素出现的次数作为下标，把键值放入list集合中。list集合为频次集合。最后创建返回的结果集，从大到小遍历list频次集，找出前k个高频元素返回即可。

题解:

执行用时: 13 ms

内存消耗: 41.4 MB

class Solution {    public int[] topKFrequent(int[] nums, int k) {        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值        HashMap<Integer,Integer> map = new HashMap<>();        // 遍历数组        for(int num : nums){            // 如果map集合包含当前元素            if (map.containsKey(num)) {                // 元素出现次数自增                map.put(num, map.get(num) + 1);            } else {                // 否则把元素出现次数设为1                map.put(num, 1);            }        }
        // 创建list集合        List<Integer>[] list = new List[nums.length + 1];        // 遍历map集合键集        for(int key : map.keySet()) {            // 获取键值出现的次数作为下标            int i = map.get(key);            // 如果list为空，则新建ArrayList            if(list[i] == null)                list[i] = new ArrayList();            // 把键放入list中            list[i].add(key);        }
        // 创建返回的结果集        int[] result = new int[k];        // 定义索引        int index = 0;        // 从大到小遍历list频次数组集合        for (int freq = list.length - 1; freq > 0; freq--) {            // 如果当前不为空            if (list[freq] != null) {                // 遍历当前list里面的元素                for (int num : list[freq]) {                    // 把元素放入结果集                    result[index++] = num;                    // 如果已排出前k个高频元素                    if (index == k) {                        // 直接返回结果集                        return result;                    }                }            }        }        // 返回结果集        return result;    }}

题目来源:力扣(LeetCode)