將同一個字符串分組在一起的最佳算法是什麼？

每種排序算法都是工作，但它是一個OVERKILL。將同一個字符串分組在一起的最佳算法是什麼？

對於像輸入：

aa 
cc 
aa 
bb 
dd 
bb 
cc

我只是需要這樣的：

aa 
aa 
cc 
cc 
bb 
bb 
dd

每個圖案的順序不是必需的。

這樣的工作有沒有這樣的算法？

來源

2013-01-15 new_perl

不會創建一個字典，關鍵是字和計數值足夠？你可以通過你的列表，如果它不在那裏添加1計數的密鑰，否則更新密鑰。 – Mathias

你只是想在這裏使用hashtable，或者更抽象的associative array。迭代輸入，如果它尚未被發現，則將其添加到散列表（如果您願意，可以使用tag）（如果它已經存在於散列表中，則將其加1）。

該算法因此在時間和空間上均爲O（n），這與您合理預期的一樣好。我建議讀一下哈希表，因爲它是一種非常有用的數據結構，出現在算法和軟件設計的各種地方。

來源

2013-01-15 01:31:22 Noldorin

比我的更詳細和實施級 - 我批准。 +1 – BlackVegetable

@BlackVegetable：啊謝謝。我發佈時沒有看到你的內容，但我們似乎只是以不同的方式解釋了相同的解決方案。 :)在任何情況下。 – Noldorin

那麼，從我頭頂開始，您可以運行一個統計每個元素存在多少的傳遞，然後創建一個新的數組，並按順序發佈它們。那將是O（n），但不是「就地」。

這樣：

// Make outputArrayCounter 
// While inputArray has elements left: 
// if current element is new, add to outputArrayCounter 
// if current element has been seen before, increment a counter associated with that 
// element. 
// Part 2... 
// Make outputArray 
// create the appropriate number of elements as found in the outputArrayCounter for 
// every different element type.

讓我們嘗試一個例子：

我們有aa bb aa cc cc dd cc的原始輸入。

我們將使我們的計數器設備，並掃描輸入。 aa，第一個元素被讀取，因爲我們以前從未遇到過aa，所以我們會將其添加到我們的計數器設備中。

計數器設備：[(aa, 1)]

現在，讓我們繼續閱讀下一個輸入，bb。它也沒有發現與添加：

計數器裝置：再次[(aa, 1), (bb, 1)]

步驟和讀aa作爲第三元件。這是在我們的設備中，並因此而不是重新加入，我們通過1

計數裝置增加與aa相關的計數器：[(aa, 2), (bb, 1)]

我會繼續給你終了計數設備狀態：

[(aa, 2), (bb, 1), (cc, 3), (dd, 1)]

現在我們經過設備並打印出每個元素的數量，很多時候，與同名的每個元素在一起。（如果順序很重要，那是一個實現細節，它將決定是否使用關聯的集合字典或某種存儲排序的雙列陣設備。這是語言特定的，但我相信你可以弄清楚。你不能，發表評論在這裏，我將描述一個解決方案。）

print aa aa bb cc cc cc dd

來源

2013-01-15 01:25:12 BlackVegetable

將同一個字符串分組在一起的最佳算法是什麼？

回答

相關問題