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

我会将其分解为两种方法。

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

第二个会return 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 
 */
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 2

你总是会先使用哈希来统计单词，这当然会使用 O(n) 时间和 O(n) space。这是第一步。

然后是如何select进入前 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 3

您必须至少将单词从头到尾迭代一次，因此您的结局不会比 O(n) 更好，其中 n 是单词大小。然后提取 m 个顶级条目（在你的例子中是 10 个）。假设您的 n 个单词中总共有 k 个独特的单词，要找到 m 个热门条目，您需要运行 max 搜索 m k 个条目的次数，这会导致 m * k 个操作，在最坏的情况下给你 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;
}

Answer 4

您可以分两步完成，使用 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() 将单词映射到它们的频率。

这 returns 一个映射，其条目按映射条目值以相反顺序流式传输和排序。然后，限制stream只保留10个元素，最后收集到一个list中。

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

Java: how to find top 10 most common String + frequency in ArrayList?

java

arraylist

hashmap

duplicates

topmost

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

Java: how to find top 10 most common String + frequency in ArrayList?

java

arraylist

hashmap

duplicates

topmost

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