原來的問題在這里：
設計一個 O(N log N) 演算法來讀入單詞串列并列印出所有字謎。例如，字串“comedian”和“demoniac”是彼此的字謎。假設有 N 個單詞，每個單詞最多包含 20 個字母。設計一個 O(N^2) 的演算法應該不會太難，但是將其降低到 O(N log N) 需要一些聰明才智。
我很困惑，因為單詞的長度不取決于 N。它是一個常數 20。所以我認為我們可以將一個單詞的運行時間乘以 N。因此結果將是 O(N)。然而，我似乎錯過了一些東西。
uj5u.com熱心網友回復：
如果他們堅持打那個O(n log n)演算法（因為我認為你可以做得更好），一種方法如下：
- 遍歷陣列并分別對每個單詞進行排序
- 保持每個排序單詞的一對一映射為其原始（例如以元組的形式）
- 按排序的單詞對新創建的串列進行排序。
- 迭代排序串列，提取具有相同排序對應項（它們現在相鄰）的單詞并列印它們。
例子：
array = ["abc", "gba", "bca"]
Sorting each word individually and keeping the original word gives:
new_array = [("abc", "abc"), ("abg", "gba"), ("abc", "bca")]
Sorting the whole array by the first element gives:
new_array = [("abc", "abc"), ("abc", "bca"), ("abg", "gba")]
Now we iterate over the above array and extract words with equal first elements in the tuple, which gives
[("abc", "abc"), ("abc", "bca")] => ["abc", "bca"]
時間復雜度分析：
- 對原始陣列的回圈是線性的
n。 - 對每個單詞進行常量排序，因為它們永遠不會超過 20 個字符。這只是
20 * log 20 = 100粗略的。 - 對整個陣列進行排序是線性的
n。 - 所得到的時間復雜性變成
O(n * log n)其中n是輸入陣列的長度。
uj5u.com熱心網友回復：
一種演算法
我們將為每一類字謎找到一個“識別符號”。識別符號應該是：
- 這個類是唯一的：沒有兩個類具有相同的識別符號；
- 可以在給定類的單個單詞時計算：給定同一類的兩個不同單詞，我們應該計算相同的識別符號。
一旦我們這樣做了，我們所要做的就是將具有相同識別符號的單詞組合在一起。有幾種不同的方法可以對具有相同識別符號的單詞進行分組；主要的兩種方式是：
- 對單詞串列進行排序，使用識別符號作為比較鍵；
- 使用“地圖”資料結構，例如哈希表或二叉樹。
你能想到一個好的識別符號嗎？
我能想到的一個識別符號是按字母順序排列的單詞字母串列。例如：
comedian --> acdeimno
dog --> dgo
god --> dgo
hello --> ehllo
hole --> ehlo
demoniac --> acdeimno
python中的實作
words = 'comedian dog god hello hole demoniac'.split()
d = {}
for word in words:
d.setdefault(''.join(sorted(word)), []).append(word)
print(list(d.values()))
[['comedian', 'demoniac'], ['dog', 'god'], ['hello'], ['hole']]
說明
這里最重要的是，對于每個單詞，我們計算了''.join(sorted(word))。這就是我之前提到的識別符號。事實上，我沒有手工撰寫前面的例子；我使用以下代碼用 python 列印它：
for word in words:
print(word, ' --> ', ''.join(sorted(word)))
comedian --> acdeimno
dog --> dgo
god --> dgo
hello --> ehllo
hole --> ehlo
demoniac --> acdeimno
那么這是什么？對于每一類字謎，我們都撰寫了一個獨特的詞來代表該類。"comedian"并且"demoniac"都屬于同一個類，用 表示"acdeimno"。
一旦我們設法做到了這一點，剩下的就是將具有相同代表的單詞分組。有幾種不同的方法可以做到這一點。在 python 代碼中，我使用了一個 python dict，一個字典，它實際上是一個將代表映射到相應單詞串列的哈希表。
另一種方法，如果您不了解地圖資料結構，則對串列進行排序，這需要 O(N log N) 次操作，使用代表作為比較鍵：
print( sorted(words, key=lambda word:''.join(sorted(word))) )
['comedian', 'demoniac', 'dog', 'god', 'hello', 'hole']
現在，屬于同一類同義詞的所有單詞都是相鄰的。剩下要做的就是遍歷這個排序串列，并對具有相同鍵的元素進行分組。這只是 O(N)。所以演算法中最長的部分是對串列進行排序。
uj5u.com熱心網友回復：
A - 您可以使用哈希表（或 python 中的字典）在 o(n) 中完成
B - 然后在每一步添加 for i in 1..sqrt(n)
這是在 ao(n) 演算法存在的情況下制作 n.sqrt(n) 的最佳方法。
0 - 讓 d=dict() 一個 python 字典
1 - 遍歷陣列：
for each word w, let s=word sorted by increasing letter value
if s already in d, add w to d[s]
if not d[s]=[w]
for i in 1.. sqrt(n) : do nothing // needed to slow from o(n) to o(n.sqrt())
2 - 列印字謎
foreach (k,l) in d
if len(l)>1 print l
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/390171.html