Bucket Sort

leetCode の「347. Top K Frequent Elements」の Discuss を読んでいて、Bucket Sort というソート方法による解法が出てきたので、今後の参考のためここにメモしておく。
https://leetcode.com/problems/top-k-frequent-elements/

ちなみに、Bucket Sort というのは、ソート対象のデータが取りうる範囲を網羅した容器 (Bucket) を用意しておき、その容器にソート対象のデータを移すことでソートする方法。

    public int[] topKFrequent(int[] nums, int k) {
        //「数値 ⇒ 出現回数」のマップ
        Map<Integer, Integer> numToCount = new HashMap<>();
        for (int num : nums) {
            numToCount.put(num, numToCount.getOrDefault(num, 0) + 1);
        }
        // 配列のインデックスを出現回数に見立てて、各数値の格納を行う。
        // この処理が「Bucket Sort」になっている。
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new ArrayList();
        }
        for (int num : numToCount.keySet()) {
            int count = numToCount.get(num);
            bucket[count].add(num);
        }

        // 求める数値の List を作成
        List<Integer> result = new ArrayList();
        for (int i = bucket.length - 1; i >= 0; i--) {
            result.addAll(bucket[i]);
            if (result.size() >= k) {
                break;
            }
        }

        // List から配列に変換
        return result.stream().mapToInt(i -> i).toArray();
    }