找到最常見的基地

-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

回答