Java:如何在ArrayList中找到前10个最常见的字符串+频率

Question

我试图找到 ArrayList 中最常见的 10 个字符串 + 它们的计数（出现频率）。

我怎样才能以最佳的时间复杂度做到这一点？

下面的代码以 （String=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

你必须从头到尾至少迭代一次单词，所以你的结局不会比O(n)更好，其中n是单词大小。然后提取m顶级条目（在您的情况下为 10 个）。假设您在n单词中总共有k个唯一单词，要找到m顶级条目，您需要对k条目运行max搜索m次，这会导致m * k操作，在最坏的情况下（当所有单词都是唯一的时）为您提供O(m * n)。总的来说，这为您提供了O(n * (m + 1))操作，或者在您的案例中O(11 * n)（搜索max加上初始分组运行的 10 次）。

这是我的尝试（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;
}

Answer 3

你总是使用哈希值来首先计算单词，这当然会使用 O（n） 时间和 O（n） 空间。这是第一步。

然后是关于如何选择前 10 名。您可以使用至少需要 O（nlogn） 时间的排序。但是有一个更好的方法，那就是使用堆。假设在您的情况下 k = 10。您需要将单词的对对象及其频率添加到大小为 k 的最小堆中，我们使用频率作为最小堆的键。如果堆已满，则从堆中删除最小元素（top），并仅在该字的频率大于堆中的顶部字时添加新的字频对。一旦我们扫描了映射中的所有单词并且堆正确更新，那么最小堆中包含的元素就是最常访问的前 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

我会把它分解为两种方法。

第一个除了创建单词频率图外什么都不做。

第二个将返回 n 个频率最高的单词。

如果您要求 n 个最常见的单词，但Map的键数少于该数字，您的代码应该怎么做？

这是您尝试JDK 8 lambdas并有效地过滤频率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;
    }
}