//Given a non-empty list of words, return the k most frequent elements.
// Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
//
// Example 1:
//
//Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
//Output: ["i", "love"]
//Explanation: "i" and "love" are the two most frequent words.
//    Note that "i" comes before "love" due to a lower alphabetical order.
//
//
//
// Example 2:
//
//Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
//Output: ["the", "is", "sunny", "day"]
//Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
//    with the number of occurrence being 4, 3, 2 and 1 respectively.
//
//
//
// Note:
//
// You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
// Input words contain only lowercase letters.
//
//
//
// Follow up:
//
// Try to solve it in O(n log k) time and O(n) extra space.
//
//
package com.llz.algorithm.algorithm2019.secondweek;

import java.util.*;

public class LeetCode_692_2 {

    class WordNode implements Comparable<WordNode> {
        String word;
        int times;

        public WordNode(String word) {
            this.word = word;
            this.times = 1;
        }


        public int compareTo(WordNode o) {
            if (this.times > o.times)
                return -1;
            else if (this.times == o.times) {
                return this.word.compareTo(o.word);

            } else {
                return 1;
            }
        }
    }

    /**
     * Using priorityQueue, time complexity is O(nlogn)+O(n)+O(k) = O(n).
     * space complexity is O(n)
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list = new ArrayList<>();
        PriorityQueue<WordNode> pq = new PriorityQueue<>(k);
        HashMap<String, WordNode> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (map.containsKey(words[i])) {
                WordNode wn = map.get(words[i]);
                wn.times++;
                map.put(words[i], wn);
            } else
                map.put(words[i], new WordNode(words[i]));
            WordNode w = map.get(words[i]);
        }

        Iterator<Map.Entry<String, WordNode>> lt = map.entrySet().iterator();
        while (lt.hasNext()) {
            pq.add(lt.next().getValue());
        }

        int j = 0;
        while (!pq.isEmpty()) {
            list.add(pq.poll().word);
            if (++j == k) break;
        }
        return list;
    }

    public static void main(String[] args) {
        LeetCode_692_2 l = new LeetCode_692_2();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        System.out.println(l.topKFrequent(words, 2));
    }
}