Given a composition with different kinds of words, return a list of the top K most frequent words in the composition.

Assumptions

• the composition is not null and is not guaranteed to be sorted
• K > = 1 and K could be larger than the number of distinct words in the composition, in this case, just return all the distinct words

Return

• a list of words ordered from most frequent one to least frequent one (the list could be of size K or smaller than K)

Examples

• Composition = ["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 2 frequent words are [“b”, “c”]
• Composition = ["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 4 frequent words are [“b”, “c”, "a", "d"]
• Composition = ["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 5 frequent words are [“b”, “c”, "a", "d"]

Solution: minHeap或maxHeap

  public String[] topKFrequent(String[] combo, int k) {
    if (combo == null || combo.length == 0) {
      return new String[0];
    }
    Map<String, Integer> hashmap = new HashMap<>();
    for (String cur : combo) {
      Integer num = hashmap.get(cur);
      hashmap.put(cur, num == null ? 1 : num + 1);
    }
    PriorityQueue<Node> pq = new PriorityQueue<>(1, new Comparator<Node>() {
      public int compare(Node a, Node b) {
        return a.val - b.val;
      }
    });
    for (Map.Entry<String, Integer> entry : hashmap.entrySet()) {
      String key = entry.getKey();
      int val = entry.getValue();
      if (pq.size() < k) {
        pq.offer(new Node(key, val));
      } else {
        if (pq.peek().val < val) {
          pq.poll();
          pq.offer(new Node(key, val));
        }
      }
    }
    int start = k - 1;
    if (k > pq.size()) {
      start = pq.size() - 1;
    }
    String[] ans = new String[start + 1];
    for (int i = start; i >= 0; i--) {
      ans[i] = pq.poll().key;
    }
    return ans;
  }
  class Node {
    String key; int val;
    public Node(String s, int v) {
      key = s;
      val = v;
    }
  }