大範圍輸入數據的最佳搜索技術

從1到1億有1億個數字，但有一個數字缺失。他們都是隨機可用的，你如何以最好的方式找到失蹤的人。大範圍輸入數據的最佳搜索技術

隨機可用的手段是他們隨機分佈於整個陣列分佈（即5984,1,10937658，20 ...）

2011-04-22 Supriya

什麼是「隨機獲得」呢？他們在陣列中嗎？是序列中的數字（即1,2,3,4，...），還是它們是隨機分佈在整個陣列中（即5984,1,10937658，...）？ – 2011-04-22 16:29:33

您的問題未指定好。也許這個http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number會有所幫助。 – 2011-04-22 19:23:30

正如我上面鏈接的問題所說，從1到N的數字之和是'（（N^2）+ N）/ 2'。所以如果你知道這個數字是從1到10億，而且有一個失蹤了，你只需將他們加起來，從預期的數字中減去總和，那就是你缺少的數字。 – 2011-04-23 19:23:31

這些只是理論上的考慮，但如果這些數字進行排序1,2,3...1B所以你只可以分裂你的電話號碼組成零件1 ... 0.5B和0.5B ... 1B然後檢查多少元素在第一組：如果有小於0.5B元素這就是手段缺失值1和0.5B之間，如果有0.5B元素這就是手段缺失值之間0.5B和1B。繼續這個過程，直到找到缺失的值。

我不知道這是否是一個非常快速的方式，但它肯定是比檢查每個值更快：d

也許它讓你在路上

來源

2011-04-22 16:46:19 Tomas

如果限制內存的關注，開始上從最初對每個數字進行異或運算。然後與1至1B異或。剩下的數字就是缺少的數字。

事情是這樣的：

Input-1 XOR Input-2 XOR Input-3 XOR Input-last XOR ... XOR 1 XOR 2 XOR...XOR 1B。

如果您有足夠的內存，請對所有數字進行排序並按順序搜索。

第一個是O(N)，而第二個是O(NlogN)

較小集合例如：

1 xor 3 xor 1 xor 2 xor 3 => 2

來源

2011-04-22 16:52:40 Jack

我不知道如果你可以使用非常優雅和快速的XOR技巧（'Ɵ（N）'空間，Ω（N）∩O（N log N）'時間） Ɵ（1）'空間，'Ɵ（N）'時間）。 – 2015-11-11 23:13:55

大範圍輸入數據的最佳搜索技術

回答

相關問題