從數組中選擇最常出現的10個字符串，java

我有一個字符串數組，我想從中找到前10個最常出現的字符串。從數組中選擇最常出現的10個字符串，java

這樣做的一種原始方式當然是循環遍歷數組一次，獲得所有不同字符串的堆棧/隊列，將這些不同的字符串存儲在一個數組中，然後檢查這個新字符串中每個字符串的次數數組出現在原始數組中，最後將值存儲爲'n'個不同的整數，其中n是不同字符串的數量。

顯然這是一個可怕的方法，當談到時間效率，所以我想知道是否有更好的方法來做到這一點。

關於與計數器每個位置創建二維數組是什麼？ – solusipse 2013-03-07 22:37:47

如果你不關心的內存，你可以建立一個哈希圖保持每個字符串的計數：通過您的所有字符串，併爲您做

myhash[mystring] += 1

每一個你循環，如果該字符串已經存在於散列中，或者

myhash[mystring] = 1

否則。

如果您認爲在恆定時間內查找哈希值的值（這不可能是真的），那麼這個算法是「僅」O(n)（但它佔用大量內存）。

2013-03-07 22:37:52 alestanis

對於這個問題，這絕對是最好的O（N）解決方案。而且我不確定你能*比這個問題的O（N）更好。 – Colleen 2013-03-07 22:39:01

@Colleen如果你的初始數組是排序的，也許你可以比'O（n）'做得更好，但是使用隨機數組肯定你不能，你必須經過每一個值 – alestanis 2013-03-07 22:40:01

你確實不能和你一樣必須至少經過一次所有字符串。 – Ingo 2013-03-07 22:40:35

如果您關心記憶，您可以對數組進行排序，然後計算每個字符串出現的次數（每個字符串將首先出現在位置i，i + 1，i + 2，...，i + k和其他地方）。

排序將花費O（n log n），而不是O（n）來計算字符串的出現次數。

2013-03-07 22:48:21 kyticka

你可以使用一個Guava Multiset將所有的字符串，然後調用Multisets.copyHighestCountFirst()只看着前10

2013-03-07 22:49:00 GuessBurger

回答