Leetcode 刷题 - 排序（day2）

Given [1,1,1,2,2,3] and k = 2, return [1,2].

实现思想：设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
具体过程步骤：

1.第一步：采用map字典，统计同一个数字出现的次数；（这一步中关键是如何统计？）
      将所给数字作为键（key）， 值（value）采用getOrDefault(key,default)函数，该函数意思是获取指定key的值，如果获取为空，则返回default（默认）值，这一步是关键；2.第二步：装桶,将键值对的 value 作为集合数组的下表，key 作为集合数组的值，从而实现桶排序；3.将题目要求的频率最多的 k 个元素存放在集合中,逆序进行；4.打印输出（或者return）结果。 代码实现：

package order;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class Order2_TopKFrequent {
    public static void main(String[] args) {
        //题目给出的数据
        int[] nums = new int[]{1, 1, 1, 2, 2, 3};
        //测试数据
        //int[] nums = new int[]{1,3,1,2,3,3,3,2,1,3,2,1,2,3};
        int k = 2;
        //1.第一步：采用map字典，统计同一个数字出现的次数
        Map frequencyForNum = new HashMap<>();
        for (int num : nums) {
            

            frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
        }
        //2.第二步：装桶,将键值对的 value 作为集合数组的下表，key 作为集合数组的值，从而实现桶排序
        List[] buckets = new ArrayList[nums.length + 1];
        for (int key : frequencyForNum.keySet()) {
            int frequency = frequencyForNum.get(key);
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(key);
            System.out.println(buckets[frequency]);
        }
        //3.将题目要求的频率最多的 k 个元素存放在集合中,逆序进行
        List topK = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
            if (buckets[i] == null)
                continue;

            
            //该步骤功能：防止出现 相同次数最多的元素时，造成返回结果超过 k 个元素
            if (buckets[i].size() <= k - topK.size()) {
                topK.addAll(buckets[i]);
            } else {
                topK.addAll(buckets[i].subList(0, k - topK.size()));
            }

            for (int j : buckets[i]) {
                System.out.println("原数：" + j + "  出现次数：" + i);
            }
        }
            //4.输出结果
            System.out.printf("出现次数最多的%d个数：n", k);
            for (int j = 0; j < topK.size(); j++) {
                System.out.print(topK.get(j) + "  ");
            }

    }
}