我想實作一個盡可能高效的搜索過濾器，它管理我的“圖書館”中的書名。搜索應按如下方式進行：
用戶鍵入書名的前 b 個字母。將回傳以輸入的字母序列開頭的書名的數量 n。k 是一個預設常數，它指定應該輸出多少書名。這意味著如果 n ≤ k，則輸出按字母順序排序的 n 個書名串列。
我目前面臨的主要問題是我不知道要選擇什么資料型別以及應該實作什么資料結構，因為我需要它盡可能高效。
一個后續問題是，如果我為此使用一個陣列，我肯定會選擇一個排序陣列，對嗎？
非常感謝任何幫助，我不要求實施。
uj5u.com熱心網友回復：
這是一個非常好的嘗試。在每次擊鍵時，您都可以準確地知道有多少本書以該前綴開頭。這是一個線性操作。因此，搜索n字符前綴需要O(n)時間。在一個簡單的 trie 實作中，要獲取書名，您需要遍歷以前綴開頭的其余路徑，但這也可以通過在 trie 的每個節點上指向以該前綴開頭的標題的指標來解決前綴（換句話說，從該節點繼續）。您也可以提前對這些指標進行排序。
因此，搜索所有以長度前綴開頭的n標題并回傳標題的整個操作將是O(n m)wherem是具有此前綴的標題的數量。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478416.html
上一篇：如何向后查找索引