從大小爲n的數組中缺少m個整數

這是一個我剛纔遇到的有趣問題，並且在解決問題時遇到了一些麻煩。從大小爲n的數組中缺少m個整數

有大小Ñ的一個未排序的整數數組存儲有數字1,2 ...，N + M ，與中號整數從它丟失。 M和N之前已知。編寫一個算法，以最有效的方式找到丟失的整數。

曾試圖映射它到尺寸Ñ + 中號的陣列，使得我個索引包含具有值我的元件，但這需要2次掃描（1用於映射， 1用於找到M缺失的數字）。

我遇到的這本書提到了單個掃描解決方案是可能的，但我無法實現它。有關如何去做這件事的任何想法？

來源

2012-11-09 sanz

你能寫下一個掃描算法嗎？謝謝。 –

這個問題似乎非常本地化，你也沒有提供任何證據表明你已經試圖自己解決問題。 – lockstock

@lockstock抱歉。我編輯了這個問題。希望這可以幫助。 – sanz

您可以使用映射到數組頂部的雙向鏈表來完成此操作。

position 1 2 3 4 5 6 ... 
next  2 3 4 5 6 7 ... 
prev  0 1 2 3 4 5 ...

在穿過輸入你指數爲對應於每個輸入數，並更新鏈接列表刪除（跳過）從鏈表該位置的位置。在輸入結束時，鏈表只包含未訪問的位置。

來源

2012-11-09 03:40:11

但是，你不必循環鏈表來打印出缺失的整數？據我瞭解，它是'1'循環嗎？ – irrelephant

@irrelephant你打賭，假設你想打印它們。我認爲，從時間複雜性的角度來看，你可以做得更好，因爲'O（N）+ O（M）'因爲直到你到達'N'的末尾，你無法知道'M '。如果你已經開始打印了，'N'的最後一個可以通過包含你已經打印的東西來破壞你的輸出。我相信你可以從空間複雜性的角度來做更好的事情，當M << N，就像上面評論中的[相當令人印象深刻的數學答案]（http://stackoverflow.com/a/3492967/1756702）似乎這樣做。 –

我不應該在那裏使用Big-O符號。我的意思是說，如果你想打印'M'，我認爲你不可能比單次通過'N'和'M'做得更好。 –

從大小爲n的數組中缺少m個整數

回答

相關問題