給出一種預處理方法，允許您在O（logn）

中查看任一方向假設您有一個詞典，它將從AA到BB的單詞。這些單詞按AA的字母順序排序（也就是說，所有的單詞都按AA排序，並且它們在BB中的相應單詞由它們正確排列）。是否可以設計方法find_BB（）和find_AA（）分別在AA和BB中取詞，並分別返回在O（logn）時間內運行的BB和AA中的相應單詞？我知道這是至少可能的find_BB（）如果單詞排序的AA，因爲那麼我們可以使用二進制搜索找到相應的BB（我們知道這在O（logn）時間運行）。但是，我似乎無法想出一種方法來安排允許對find_BB和find_AA進行O（logn）查找的字典。它甚至有可能嗎？給出一種預處理方法，允許您在O（logn）

來源

2014-09-22 Bob John

我不明白這種情況。「從AA到BB的字典」是什麼意思？AA和BB是什麼？話？詞集？我最好的猜測是你想要通過這兩個元組對索引字對進行索引。在這種情況下，您可以添加冗餘。複製陣列並按AA排列其中一個副本，另一個由BB – 2014-09-22 22:57:34

@NiklasB排序。這就是他的意思，他有一種哈希映射，通過集合AA中的單詞對集合BB中的單詞進行索引。如果AA和BB不相交，爲什麼不存儲這兩個詞典的聯合。如果不是，則只需將兩個字典存儲爲兩種映射方式即可。 – 2014-09-22 23:01:04

@AshuPachauri你怎麼知道這是什麼意思？ – 2014-09-23 00:05:01

你在問你是否可以有一張允許向前和向後查找的地圖。這可以通過保存兩張地圖來完成：一張從AA到BB，另一張從BB到AA。如果您使用排序列表來實現映射，那麼您的查找都是O（log n），或者如果您使用兩個散列表，則兩個查找都是O（1）。

來源

2014-09-22 23:02:54

我不禁要提到，使用String鍵映射哈希表不是最有效的數據結構。在散列表中搜索的分攤成本爲O（1）。沒有考慮到字符串比較的非恆定成本。有爲這個特定任務設計的結構 - [嘗試]（http://en.wikipedia.org/wiki/Trie）和其他基數T恤。 – Aivean 2014-09-22 23:16:08

我想提到的第一件事是，在排序的字符串數組中執行二進制搜索將花費超過O（log n），因爲字符串比較本身不是常量。

其次，你沒有發佈任何內存使用限制。嚴格地說，有兩個排序陣列，一個用於AA-> BB，另一個用於BB-> AA將解決您的任務。如果需要，可以將這兩個數組封裝在一個數據結構中。

最後。您是否考慮過更高效的數據結構，如Trie？您可以爲AA和BB中的元素構建單個trie，對於每個存儲最多兩個值的葉子。如果葉子是AA的關鍵字，則存儲相應的BB值（標記爲BB），反之亦然。

來源

2014-09-22 23:06:18 Aivean

給出一種預處理方法，允許您在O（logn）

回答

相關問題