我有一个字符串数组，我想从中找到前 10 个最常出现的字符串。
这样做的一种原始方法当然是遍历数组一次，获取所有不同字符串的堆栈/队列，将这些不同的字符串存储在一个数组中，然后检查这个新数组中每个字符串在原始数组，最后将值存储在“n”个不同的整数中，其中 n 是不同字符串的数量。
显然，就时间效率而言，这是一种可怕的方法，所以我想知道是否有更好的方法来做到这一点。
问问题
1231 次
3 回答
4
如果您不关心内存，则可以构建一个包含每个字符串的计数的哈希映射：您循环遍历所有字符串并为您执行的每个字符串
myhash[mystring] += 1
如果字符串已经存在于哈希中，或者
myhash[mystring] = 1
除此以外。
如果您认为在哈希映射中查找值是在恒定时间内进行的（这不可能是真的），那么这个算法是“唯一的” O(n)（但它会占用大量内存）。
于 2013-03-07T22:37:52.547 回答
2
如果您关心内存，您可以对数组进行排序，然后轻松计算每个字符串出现的次数（每个字符串将首先出现在位置 i、i+1、i+2、...、i+k 和其他位置） .
排序将花费 O(n log n)，而不是 O(n) 来计算字符串的出现次数。
于 2013-03-07T22:48:21.903 回答
1
您可以使用Guava Multiset添加所有字符串，然后Multisets.copyHighestCountFirst()仅查看前 10 个字符串
请参阅此问题以获取示例
于 2013-03-07T22:49:00.297 回答