这是一个 homework问题。
我的字符串可以包含很多字符，我需要找出字符串中重复次数最多的字符。
Ex: str="sample string contains aaaaaaaaaa #12"; Here most repeated char is 'a'
我的代码:(算法)
- Initialized 2D array with size 127 (ASCII) chars. arr[127][2]
- Parsed the string, incrementing the ASCII index of array with respective values.
> for(int i=0; i<str.length(); i++)
> arr[str.charAt(1)][1] += 1;
- Finally, going through the array to find out the max value of arr[x][1]
这个问题，需要O(n)来解决。
当字符串大小非常大时，我正在寻找更好的性能。
谢谢!
最佳答案
我可以想象一个类似 Boyers-Moore 的算法用于字符串匹配。您已经识别了 n 个字符的重复序列，然后要检查从位置 i 开始的序列是否更长，那么您只需要检查位置 i +n 查看它是否与位置 i 处的字符相同。如果不是，则从位置 i+1 开始检查；如果是，那么您开始循环这两点之间的字符，看看它们是否都相同。如果你做得正确，你最终可能会跳过很多字符串。最坏的情况，它仍然是 O(n)，因为它必须如此，但最好的情况你可以跳过很多。
就空间要求而言:只需跟踪最长的游程长度和字符(或起始位置)。您不需要二维数组。
关于java - 性能 - 用Java进行字符串操作以获得最多重复的字符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9595725/