Java：如何在ArrayList中找到前10個最常見的String +頻率？

Question

我想在ArrayList +他們的計數（發生頻率）中找到前10個最常見的字符串。

我該如何處理最佳的時間複雜度？

下面的代碼發現的形式的最常見單詞+頻率（字符串= INT）

例如該= 2

public static Entry<String, Integer> get10MostCommon(WordStream words) { 

    ArrayList<String> list = new ArrayList<String>(); 
    Map<String, Integer> stringsCount = new HashMap<>(); 
    Map.Entry<String, Integer> mostRepeated = null; 

    for (String i : words) { 
     list.add(i); 
    } 

    for (String s : list) { 
     Integer c = stringsCount.get(s); 
     if (c == null) 
     c = new Integer(0); 
     c++; 
     stringsCount.put(s, c); 
    } 

    for (Map.Entry<String, Integer> e : stringsCount.entrySet()) { 
     if (mostRepeated == null || mostRepeated.getValue() < e.getValue()) 
     mostRepeated = e; 
    } 
    return mostRepeated; 
    } 

Answer 1

你可以做的兩個步驟，使用Java 8流：

Map<String, Long> map = list.stream() 
     .collect(Collectors.groupingBy(w -> w, Collectors.counting())); 

List<Map.Entry<String, Long>> result = map.entrySet().stream() 
     .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) 
     .limit(10) 
     .collect(Collectors.toList()); 

第一物流通過映射的話它們的頻率使用Collectors.groupingBy()以及Collectors.counting()。

這將返回一個地圖，其條目將按照相反的順序進行流式傳輸並按地圖條目值排序。然後，流限制爲僅保留10個元素，最終收集到列表中。

Answer 2

我會分解成兩種方法這一點。

第一個什麼都不做，只是創建詞頻的地圖。

第二個會返回n個最高頻率的單詞。

如果您詢問n個最頻繁的單詞，但Map的鍵數少於該數字，您的代碼應該做什麼？

這是您嘗試JDK 8 lambda並有效過濾頻率Map的機會。

import java.util.Arrays; 
import java.util.LinkedHashMap; 
import java.util.List; 
import java.util.Map; 

/** 
* Calculate word frequencies from a List of words 
* User: mduffy 
* Date: 3/14/2016 
* Time: 1:07 PM 
* @link http://stackoverflow.com/questions/35992891/java-how-to-find-top-10-most-common-string-frequency-in-arraylist/35993252#35993252 
*/ 
public class WordFrequencyDemo { 

    public static void main(String[] args) { 
     List<String> words = Arrays.asList(args); 
     Map<String, Integer> wordFrequencies = WordFrequencyDemo.getWordFrequencies(words); 
     System.out.println(wordFrequencies); 
    } 

    public static Map<String, Integer> getWordFrequencies(List<String> words) { 
     Map<String, Integer> wordFrequencies = new LinkedHashMap<String, Integer>(); 
     if (words != null) { 
      for (String word : words) { 
       if (word != null) { 
        word = word.trim(); 
        if (!wordFrequencies.containsKey(word)) { 
         wordFrequencies.put(word, 0); 
        } 
        int count = wordFrequencies.get(word); 
        wordFrequencies.put(word, ++count); 
       } 
      } 
     } 
     return wordFrequencies; 
    } 
} 

Answer 3

您總是會先用散列來計算單詞，這當然會使用O（n）時間和O（n）空間。這是第一步。

然後它涉及到如何選擇前10名。您可以使用至少需要O（nlogn）時間的排序。但是有一個更好的方法，那就是使用堆。假設你的情況k = 10。您需要將單詞的對象和它的頻率添加到大小爲k的最小堆中，我們將頻率用作最小堆的關鍵字。如果堆已滿，則僅從堆中刪除最小元素（頂部），並僅在此字的頻率大於堆中頂部字的頻率時才添加新的字 - 頻率對。一旦我們掃描了地圖中的所有單詞並正確更新了堆，那麼最小堆中包含的元素就是前k個最頻繁的元素。以下是示例代碼。只需稍微修改一下代碼就可以使用ArrayList而不是數組來完成工作。

class Pair { 
    String key; 
    int value; 

    Pair(String key, int value) { 
     this.key = key; 
     this.value = value; 
    } 
} 

public class Solution { 
    /** 
    * @param words an array of string 
    * @param k an integer 
    * @return an array of string 
    */ 

    private Comparator<Pair> pairComparator = new Comparator<Pair>() { 
     public int compare(Pair left, Pair right) { 
      if (left.value != right.value) { 
       return left.value - right.value; 
      } 
      return right.key.compareTo(left.key); 
     } 
    }; 

    public String[] topKFrequentWords(String[] words, int k) { 
     if (k == 0) { 
      return new String[0]; 
     } 

     HashMap<String, Integer> counter = new HashMap<>(); 
     for (String word : words) { 
      if (counter.containsKey(word)) { 
       counter.put(word, counter.get(word) + 1); 
      } else { 
       counter.put(word, 1); 
      } 
     } 

     PriorityQueue<Pair> Q = new PriorityQueue<Pair>(k, pairComparator); 
     for (String word : counter.keySet()) { 
      Pair peak = Q.peek(); 
      Pair newPair = new Pair(word, counter.get(word)); 
      if (Q.size() < k) { 
       Q.add(newPair); 
      } else if (pairComparator.compare(newPair, peak) > 0) { 
       Q.poll(); 
       Q.add(new Pair(word, counter.get(word))); 
      } 
     } 

     String[] result = new String[k]; 
     int index = 0; 
     while (!Q.isEmpty()) { 
      result[index++] = Q.poll().key; 
     } 

     // reverse 
     for (int i = 0; i < index/2; i++) { 
      String temp = result[i]; 
      result[i] = result[index - i - 1]; 
      result[index - i - 1] = temp; 
     } 

     return result; 
    } 
} 

Answer 4

你將不得不從開始迭代話來結束至少一次，這樣你就不會比O(n)，其中n是字大小結束越好。然後提取m頂級條目（在你的情況下爲10）。假設你在你的總n話k獨特的話，找m頂部條目，您需要在k條目，從而導致m * k操作運行max搜索m倍，讓您O(m * n)在最壞的情況下（當所有的話都是唯一的） 。總共，這給你O(n * (m + 1))操作，或O(11 * n)你的情況（10次max搜索加上初始分組運行）。

這裏是我的嘗試（JDK8 +，未測試）：

public static Collection<Map.Entry<String, Integer>> topOccurences(List<String> words, int topThreshold) { 
    Map<String, Integer> occurences = new HashMap<>(); 
    words.stream().forEach((word) -> { 
     int count = 1; 
     if (occurences.containsKey(word)) { 
      count = occurences.get(word) + 1; 
     } 
     occurences.put(word, count); 
    }); 

    List<Map.Entry<String, Integer>> entries = new LinkedList<>(occurences.entrySet()); 
    List<Map.Entry<String, Integer>> tops = new LinkedList<>(); 
    Comparator<Map.Entry<String, Integer>> valueComp = Comparator.comparing((Map.Entry<String, Integer> t) -> t.getValue()); 
    int topcount = 0; 
    while (topcount < topThreshold && !entries.isEmpty()) { 
     Map.Entry<String, Integer> max = Collections.max(entries, valueComp); 
     tops.add(max); 
     entries.remove(max); 
     topcount++; 
    } 
    return tops; 
}