package 队列.优先级队列;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
/**
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 * 
 * @author Huangyujun
 *
 */
public class _347_前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
//        List<Integer> res = new ArrayList<Integer>();
        // 键-元素数值，值-数量
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
//            if (map.containsKey(nums[i])) {
//                int frequency = map.get(nums[i]) + 1;
//                map.put(nums[i], frequency);
//            } else {
//                map.put(nums[i], 1);
//            }
            // 优化一下：
            int frequency = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], frequency);
        }
//        // 使用集合，将键装到集合【并用集合Collections的排序，通过map的get() 的频率进行比较后存储】
//        List<Integer> list = new ArrayList<Integer>(map.keySet());
//        // 排序
//        Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
//        for (int i = 0; i < k; i++) {
//            res.add(list.get(i));
//        }
        // 优化【直接使用map开启遍历，不再使用Collections重复遍历】
        // 优化点【使用小根堆】
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            //箭头函数【lambda表达式】的话，执行效率并不高
            @Override
            public int compare(int[] o1, int[] o2) {    
                return o1[1] - o2[1];
            }        
        });
        /**
         * 优先队列存储方式queue.offer(new int[] { num, count });？？？看不懂，为啥是两个呢？？？
         * 跟他定义成数组直接相关啦【没定义成数组【又因为num、count 是同类型的，so 定义成同类数组很好】，肯定存储一个】
         */
        //前k个【】
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
//            if (queue.size() == k) {
//                if (queue.peek()[1] < count) {
//                    queue.poll();
//                    queue.offer(new int[] { num, count });
//                }
//            } else {
//                queue.offer(new int[] { num, count });
//            }
            queue.offer(new int[] { num, count });
            if(queue.size() > k) {
                queue.poll();
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll()[0];
        }
//        int[] ans = new int[k];
//        for(int i = 0; i < k; i++) {
//            ans[i] = res.get(i);
//        }
        return ans;
    }
}