1

我有一个字符串源（假设是一个文本文件），并且许多字符串重复了多次。我需要按出现次数递减的顺序获取前 X 个最常见的字符串。

首先想到的想法是创建一个可排序的 Bag（类似于org.apache.commons.collections.bag.TreeBag）并提供一个比较器，它将按照我需要的顺序对条目进行排序。但是，我无法弄清楚我需要比较的对象类型是什么。它应该是某种内部映射，它结合了我的对象（字符串）和出现次数，由 TreeBag 内部生成。这可能吗？

或者我会更好地通过简单地使用哈希图并按值对其进行排序，例如Java sort HashMap by value

4

2 回答 2

0

为什么不将字符串放在地图中。将字符串映射到它们在文本中出现的次数。在第 2 步中，遍历映射中的项目并继续将它们添加到大小为 X 的最小堆中。如果堆已满，则始终先提取 min，然后再插入。
需要 nlogx 时间。

否则在第 1 步之后按出现次数对项目进行排序并取前 x 个项目。树形图在这里会很有帮助:)（我会添加一个指向 javadocs 的链接，但我在平板电脑中）需要 nlogn 时间。

于 2012-03-22T04:53:53.283 回答
0

使用番石榴 TreeMultiset，只需使用Multisets.copyHighestCountFirst.

于 2012-03-22T09:23:03.643 回答