找到最常见的基地

-2

假设我需要比较'n'值并找出最常见记录中发生的最常见的范围，我们如何有效地做到这一点？例如：假设值是
AABBCCDD
AABBEEFF
QWBBGGUU
SDBBGGOO
AABBGGHH找到最常见的基地

在这种情况下，输出应为
AABB。

我们只需要最常用的上一个值。所以输出将不会是
BBGG

可以使用hashmaps计算出一种方法，但是如果可能的话，我们需要找到更好的方法。

这听起来像是作业;你试过什么了？ –

如果列表中有另一个元素“AABCCCDD”，那么正确答案是“AABB”（分数为3，长度为4）或“AAB”（分数为4和长度） 3）？如果是后者，那么为什么正确答案并不总是空字符串（得分为'n'且长度为0）？简而言之，您需要先确定要查找的内容，然后才能确定如何有效地找到它。 –

'BB'出现在所有的值中。为什么不是这个答案？ –

要找到最长前缀常见字符串的至少50％：在琴弦

运行一次，看看每个的第一个字符，统计每个字符出现的次数（甚至更好，使用多数发现算法）。
如果您没有找到大多数的第一个字母，解决方案是空字符串。
如果您确实找到了多数的第一个字母，请重复检查第二个字母（计算所有首字母大写的所有字符串的第二个字母，但是在决定它是否仍然是多数的时候，当然必须包含所有字符串）。最终你不会再找到多数，返回你所拥有的任何东西。

完全不同的方法：建立您的所有字符串的特里，并在每个节点保持多少字符串有前缀的计数。然后从根部走下树，在每个步骤中查找大于或等于n/2的计数。如果你找到一个，按照它。如果你不这样做，停下来。如果你的规则比“多数人共享的最长前缀”更复杂，那么你也可以看看Trie的其他地方。

2012-05-09 09:39:49

回答