LeetCode_34_TopKFrequentElements

LeetCode

发布日期: 2022-04-08

更新日期: 2022-05-20

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

1. question: 前K个高频元素（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

示例 1:

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

示例 2:

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

提示：

1
2
3

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

2. answers

这道题分为两部分，一部分是统计元素数量，另一部分是对元素数量进行排序，取前k个。

统计元素数量可以采用Map数据结构来做；对Map元素进行排序，这里参考博客，可以利用堆来做（优先级队列）。

代码如下所示：

public class Solution_0031 {

    public static int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[k];

        for(int i: nums) {

            if(map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }

        }

        // 对Map进行排序，参考其他博客，采用优先级队列存储元素进行排序。
        // 注意补充数据结构：优先级队列，堆
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        // 根据map的value值正序排，相当于一个小顶堆
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        for (int i = k - 1; i >= 0; i--) {
            result[i] = queue.poll().getKey();
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

        int[] nums = {1, 1, 1, 2, 3, 3};

        int[] result = topKFrequent(nums, 2);

        for(int i: result) {
            System.out.println(i);
        }
    }
}

另外，参考题解，可采用桶排序来做。在统计完频率后，新建一个新数组，数字的频率就是该数字在新数组中的下标，因为不同数字的频率可能会重复，所以新数组是一个List数组。频率越高，其下标位置越大。最后逆序遍历新数组即可。

public class Solution_0031_02 {

    public static int[] topKFrequent(int[] nums, int k) {

        int[] r = new int[k];

        Map<Integer, Integer> result = new HashMap<>();

        // 统计元素个数
        for(int i: nums) {

            if(result.containsKey(i)) result.put(i, result.get(i) + 1);
            else result.put(i, 1);

        }

        // 排序，并统计前k个。
        Set<Integer> integers = result.keySet();

        // 定义数组，用于存放比较结果。本意是数组下标表示对应的频率，数组值表示对应的元素。
        // 但是频率可能会重复，因此，数组值表示对应的List，可存储多个元素。即是List数组
        // 另外，是前k的元素，所以k一定会大于等于List内部元素个数的，否则就会出现歧义，这是不允许的。
        // 注意，是以频率为下标，所以频率最多为length长度，但是下标此时就是length长度，所以数组总长度必须+1
        ArrayList<Integer>[] temp = new ArrayList[nums.length + 1];

        ArrayList<Integer> list;

        for(Integer i: integers) {

            int index = result.get(i);

            // 表示当前位置还没存储元素
            if(temp[index] == null) {
                list = new ArrayList<>();
            } else {
                list = temp[index];
            }

            list.add(i);
            temp[index] = list;
        }

        // 取top K个元素，注意数量和下标的关系
        k --;
        while(k >= 0) {

            // 下标越大，即次数越多，所以逆序遍历
            for (int i = temp.length - 1; i > -1 ; i--) {

                if(temp[i] == null) continue;

                for(Integer j: temp[i]) {

                    r[k--] = j;
                    // 在循环里面不用判断是否k会溢出，因为此时是在一个下标里面，这里面的数出现的次数是一样的，
                    // 肯定要么全满足条件，要么都不满足条件
                }

                // 一个频率的数值全部遍历完毕。
                if(k < 0) break;
            }
        }

        return r;
    }

    public static void main(String[] args) {

//        int[] nums = {1,1,1,2,2,3};
//        int k = 2;

        int[] nums = {1};
        int k = 1;

        int[] result = topKFrequent(nums, k);

        for(int i: result){
            System.out.print(i + "\t");
        }
    }
}