java - 如何对字符串列表进行排序并在 Java 中找到 1000 个最常见的值

Question

在 Java 中(无论是否使用外部库)，我需要获取大约 500,000 个值的列表并找到最常出现的(模式)1000。尽我所能将复杂性保持在最低限度。

到目前为止我已经尝试过，做一个散列，但我做不到，因为它必须是向后的 key=count value =string，否则当获得前 1000 名时，我的复杂性将是垃圾。并且向后的方式并不是很好，因为当我搜索我的字符串能够将其删除并将其插入更高的位置时，我的插入会非常复杂...

我试过使用二叉搜索树，但它有同样的问题，即数据将用于排序，无论是在计数上还是在字符串上。如果它在字符串上，那么获取前 1000 名的计数是不好的，反之亦然，插入也是不好的。

我可以先对列表进行排序(按字符串)，然后遍历列表并保持计数，直到它更改字符串。但是我应该使用什么数据结构来跟踪前 1000 名？

谢谢

Answer 1

我会先创建一个 Map<String, Long>存储每个单词的频率。然后，我将按值降序对这张 map 进行排序，最后我将保留第一个 1000。条目。

在代码中:

List<String> top1000Words = listOfWords.stream()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
    .entrySet().stream()
        .sorted(Map.Entry.comparingByValue().reversed())
        .limit(1000)
        .map(Map.Entry::getKey)
        .collect(Collectors.toList());

您可能会发现将上述内容分为 2 个步骤会更简洁:首先收集到频率图，然后按值对其条目进行排序并保留前 1000 个条目。