difficulty: Hard tags:

  • Heap
  • Data Structure Design
  • Hash Table title: Top K Frequent Words II

Top K Frequent Words II

Problem

Metadata

Description

Find top k frequent words in realtime data stream.

Implement three methods for Topk Class:

  1. TopK(k). The constructor.
  2. add(word). Add a new word.
  3. topk(). Get the current top k frequent words.

Notice

If two words have the same frequency, rank them by alphabet.

Example

  1. TopK(2)
  2. add("lint")
  3. add("code")
  4. add("code")
  5. topk()
  6. >> ["code", "lint"]

题解

此题较难，实际上和 Redis 的有序集合类似，综合使用字典和排序集合可完美解决。

Java

  1. public class TopK {
  2.     private int k;
  3.     private Map<String, Integer> wordFreq = null;
  4.     private TreeSet<String> topkSet = null;
  6.     class TopkComparator implements Comparator<String> {
  7.         public int compare(String s1, String s2) {
  8.             int s1Freq = wordFreq.get(s1), s2Freq = wordFreq.get(s2);
  9.             if (s1Freq != s2Freq) {
  10.                 return s2Freq - s1Freq;
  11.             } else {
  12.                 return s1.compareTo(s2);
  13.             }
  14.         }
  15.     }
  17.     /*
  18.     * @param k: An integer
  19.     */public TopK(int k) {
  20.         // do intialization if necessary
  21.         this.k = k;
  22.         wordFreq = new HashMap<String, Integer>(k);
  23.         topkSet = new TreeSet<String>(new TopkComparator());
  24.     }
  26.     /*
  27.      * @param word: A string
  28.      * @return: nothing
  29.      */
  30.     public void add(String word) {
  31.         // write your code here
  32.         if (wordFreq.containsKey(word)) {
  33.             if (topkSet.contains(word)) {
  34.                 topkSet.remove(word);
  35.             }
  36.             wordFreq.put(word, wordFreq.get(word) + 1);
  37.         } else {
  38.             wordFreq.put(word, 1);
  39.         }
  41.         topkSet.add(word);
  42.         if (topkSet.size() > k) {
  43.             topkSet.pollLast();
  44.         }
  45.     }
  47.     /*
  48.      * @return: the current top k frequent words.
  49.      */
  50.     public List<String> topk() {
  51.         // write your code here
  52.         List<String> result = new ArrayList<String>(k);
  53.         Iterator<String> it = topkSet.iterator();
  54.         while (it.hasNext()) {
  55.             result.add(it.next());
  56.         }
  58.         return result;
  59.     }
  60. }

源码分析

略

复杂度分析

待续