我正在寻找最有效的（时间和空间）算法来计算给定字符串的字符频率。
想到的最简单的算法是有一个要搜索的标志数组（大小=不同字符的数量）并增加相应索引的计数器。这在线性时间内有效。唯一的问题是标志数组的空间要求，如果需要所有 ASCII 字符，它可以达到 256 个。
有没有更好的算法，可以节省空间/时间？
问问题
1288 次
1 回答
3
如果您使用哈希表来存储计数器，您需要与字符串中不同字符的数量成比例的空间，并且您仍然可以在线性时间内运行计算。很容易看出，您无法比线性时间更好，因为您需要至少查看每个字符一次。
然而，在实践中，如果您的字符串真的只使用一个字节来存储一个字符（即它不是 Unicode），那么您的“标志数组”将只有大约 1 kb，因此可能是最好的选择，因为它没有 (常数因子）哈希表的时间和空间开销。
于 2012-08-27T01:37:00.143 回答