java - 根据每个字符的出现次数有效地对字符串进行排序

Question

我正在尝试根据每个字符出现的次数对字符串进行排序，最常见的在开头，最稀有的在结尾。排序后，我需要删除所有字符重复。因为示例总是更清晰，所以程序应该执行以下操作:

String str = "aebbaaahhhhhhaabbbccdfffeegh";
String output = sortByCharacterOccurrencesAndTrim(str);

在这种情况下，“sortByCharacterOccurrencesAndTrim”方法应该返回:

String output = "habefcdg"

在 2 个字符出现相同的情况下，它们在返回字符串中的顺序无关紧要。所以“habefcdg”也可以等于“habfecgd”，因为“f”和“e”都出现了 3 次，而“d”和“g”都出现了一次。

"habefcdg" would effectively be the same as "habfecgd"

注意:我想指出，在这种情况下性能很重要，所以我更喜欢尽可能高效的方法。我这样说是因为字符串长度的范围可以从 1 到最大长度(我认为这与 Integer.MAX_VALUE 相同，但不确定)，所以我想尽量减少任何潜在的瓶颈。

Answer 1

“一个映射和几个 while 循环”当然是最简单的方法，而且可能会非常快。想法是:

for each character
    increment its count in the map
Sort the map in descending order
Output the map keys in that order

但是 100,000,000 次 map 查找可能会变得非常昂贵。您可以通过创建一个包含 65,536 个整数计数(如果是 ASCII，则为 128 个字符)的数组来加速它。然后:

for each character
    array[(int)ch] += 1

然后，您遍历该数组并创建一个具有非零计数的字符映射:

for i = 0 to 65535
    if array[i] > 0
        map.add((char)i, array[i])

然后按降序对 map 进行排序，并按该顺序输出字符。

这可能会执行得更快，因为索引数组 100,000,000 次可能比执行 100,000,000 次 map 查找快得多。