算法建議 - 在號碼列表上搜索

Question

我有7位數字的號碼列表。我需要在列表中執行搜索操作。程序的輸入將如此5xx9xx1。至少3位數字是已知的。已知數字的索引並不重要。你會建議哪種算法？我不想用'like'查詢在數據庫上搜索。

Answer 1

我能想到的通過一些通配符搜索參數來匹配集合上的元素的唯一方法是遍歷列表並找到匹配的元素。

如果結果太慢，您還可以將列表分開並執行並行搜索。

Answer 2

我假設您有初始數字列表已排序。如果它沒有排序，你最好將它排序，因爲使用排序列表，你可以用一個非常直的算法得到數字。但是，如果這不是時間關鍵操作，則最好使用散列表或B-Tree數據結構。 B-Tree可以爲您提供log（n）查詢時間。實施起來更容易。

隨着排序列表，你可以跳轉到正確的元素直接，如果輸入指定搜索的位置和價值，即如果輸入稱只尋找具有5，在位置69和1號碼，分別爲3和0，您可以直接跳轉到索引5,000,000，並且您不必查找5,999,999以外的值。

關鍵洞察在於這樣一個事實：如果你在尋找在X位置的數字（I），你發現在那個位置上的第一個這樣的號碼N，那麼接下來連續10^X-1數字將有I在同一位置。將有I在X的下一組號碼將在索引N + 10^(X+1)。

例如，如果你正在尋找與5數字在2位置，如果你是在說10000500，那麼您可以在的東西，將匹配條件讀取下一10^2-1(99)號碼。下一組位於10000500 + 10^3 = 100001500。

在你的問題，雖然你有多個這樣的條件，所以你開始在最高位置的數字，然後進一步下降到更小的位置，並跳轉到數字集。如果下一個跳轉到的數值大於上一個數字所允許的範圍，則跳轉到上一個數字指向的數值。

例如，如果你在2位置和3與5尋找數在1位置，你開始在10000530。接下來的10^1號碼將符合您的標準。單獨的3的下一個集合將在10000530 + 10^2 = 10000630，但是超過5在位置2設置的限制，即99。所以你跳轉到5指向的下一個集合，即10001530。

這種方法在時間上是線性的，w.r.到輸出集，所以你可以有一個巨大的輸入，如果你的輸出是非常小的，這個方法會非常快速。如果您使用B-Tree或某些此類方法，則它們將取決於輸入大小。