查找數組中缺失整數的最有效方法

給定一個整數1到100的數組（隨機插入），並從數組中取出一個整數。找到缺失的整數的最有效方法是什麼？查找數組中缺失整數的最有效方法

2014-01-12 KingKongFrog

的可能重複[最快的方式找到的數字陣列失蹤數] （http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers） – baci

在2.8k代表，人們會期望用戶知道以顯示在一個問題中完成的一些研究的證明... – Dukeling

正如你所知道的整數，使所有這些的總和：

(1+N)*N/2 = (1+100)*100/2 = 5050

而現在那些。減去是在陣列中的總和（S」）。差異將是你尋找的一個缺失的數字（所以x = 5050 - S'）。

時間複雜度是O（N），不能更快解決，因爲你肯定需要讀一次數組。

來源

2014-01-12 21:46:06

這可能不是最佳答案，考慮到N非常大，所以你可以有一個溢出。 –

這是最佳選擇，因爲我們在此討論1..100範圍。如果我們有更大的nunmbers，我們仍然可以使用它，但是實現我們自己的基於數組的大整數的整數類。 –

MZetko已經回答的基本情況，但這裏有4級到這個其他的解決方案，其中對陣列進行排序或無序

https://github.com/KartikTalwar/Algorithms/blob/master/Arrays/Find%20only%201%20missing%20number%20from%20an%20array/Find1MissingElementFromArray.py

來源

2014-01-12 21:48:46 Kartik

而不僅僅是提供一個鏈接，[這將是更可取的]（http://meta.stackexchange.com/a/8259）在這裏包括答案的基本部分，並且只提供鏈接以供其他參考。如果你不能完成這個任務，你應該考慮簡單地[留下評論]（http://stackoverflow.com/privileges/comment）而不是發佈答案。 – Dukeling

下次會記住這一點，但在我的辯護中，我在鏈接中寫下了答案 – Kartik

請記住，帖子在這裏是爲了長遠的目的 - 不要只寫新帖以符合準則，還要編輯現有的帖子（即這篇文章）。 – Dukeling

查找數組中缺失整數的最有效方法

回答

相關問題