package sort;

import java.util.*;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 */
public class a_347 {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //将数组中的值放在一个Map集合中,其中,数组中的值存放在key键中,value为该值的出现次数
        Map<Integer, Integer> frequencyForNum = new HashMap<>();
        for (int num : nums) {
            frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
        }
        //构造若干个桶,每个桶存储频率相同的数,桶的下标值代表出现的频率数,即第i个桶中存储的数出现的频率为i
        List<Integer>[] buckets = new ArrayList[nums.length + 1];//buckets[0]不存储数据，因为没有出现频率为0的数
        for (int key : frequencyForNum.keySet()) {
            int frequency = frequencyForNum.get(key);
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(key);
        }
        //从后向前遍历若干个桶,最先得到的k个数就是出现频率最多的的k个数。
        List<Integer> topK = new ArrayList<>();
        for (int i = buckets.length-1; i >= 0 && topK.size() < k; i--) {
            if (buckets[i] != null) {
                topK.addAll(buckets[i]);
            }
        }
        return topK;
    }
}