package week02;


import java.util.*;

/**
 * @创建人 luoxiang
 * @创建时间 2019/6/12  9:30
 * @描述 LeetCode :  692. 前K个高频单词        https://leetcode-cn.com/problems/top-k-frequent-words/
 */
public class TopKFrequentWords692 {
    public static void main(String[] args) {


        String[] strs = new String[]{"i", "love", "leetcode", "i", "love", "coding"};
        String[] strs2 = new String[]{"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        final List<String> list = new TopKFrequentWords692().topKFrequent(strs, 2);
        final List<String> list2 = new TopKFrequentWords692().topKFrequent(strs2, 4);
        for (String s : list) {
            System.out.print(s + ",");
        }
        System.out.println();
        for (String s : list2) {
            System.out.print(s + ",");
        }

    }

    /**
     *  Method 1 : 使用优先队列， 需要重写 优先队列的比较方式
     *  时间复杂度 : O(N)    ;
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
        PriorityQueue<String> pq = new PriorityQueue(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        }
        );
        List<String> list = new LinkedList<>();
        for (String entry : map.keySet()) pq.offer(entry);
        for (int i = 0; i < k; i++) list.add(pq.poll());
        return list;
    }

    public List<String> topKFrequent2(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
                (a, b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue()
        );
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
        }
        List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            list.add(pq.poll().getKey());
        }
        return list;
    }


}