設計O（n）算法找到一個不在範圍[0，n-1]內的數字

數組A在range [0,n-1]中包含n-1個唯一整數，即該範圍內有一個數字不在A 。設計一個O(n)算法找出這個數字。除陣列A本身之外，您只能使用O(1)附加空間。設計O（n）算法找到一個不在範圍[0，n-1]內的數字

任何人都可以幫忙嗎？

2014-09-11 Anqi Zhang

薩姆向上從0到n-1，然後發現在陣列的總和數量和丟失的數目是總和 - 陣列的總和

說明：如果總和0 + 1 + 2 + ... + n-1，並且數組也有所有這些數字，除了一個，所以當你添加到0 + 1 + 2 + ... + n-1數組中所有帶有「 - 」前綴的數字時，每個數字將取消他「+」對應物，所以你將留下與陣列中沒有對應物的「+」，所以這是缺少的數字

注意：存儲數字是log（n）位，但在大多數地方（我已經看到）他們不會以位分辨率說話，並且存儲數字是O（1）空間，所以我T依賴它是如何在你的問題中定義

2014-09-11 10:05:17

值得注意的是，增加'n'整數並不佔用一個固定的空間，而是一個'log（n）'空間。表示數字「n」所需的位數是「log2（n）」。 – 2014-09-11 10:25:10

這取決於你認爲的空間複雜性，從我所知道的存儲數字是O（1），但你是對的，這取決於它在問題中的定義 – 2014-09-11 10:33:02

編輯我的回答 – 2014-09-11 10:34:46

鑑於名單一個（尺寸100）和b在0-99範圍內唯一整數的（99號）與隨機排序。

a = RandomSample[Range[0, 99]] 
b = Take[RandomSample[Range[0, 99]], 99]

查找b缺少的元素。

element = Total[a]-Total[b]

使用的語言是Mathematica。

2014-09-11 10:21:15 Margus

回答