如果你還沒有看過上一篇文章，請先移步看問題描述。

擴展問題二：至多掃描一遍序列，求出丟失的兩個數字。??

不管用什么方法，可以肯定的是我們至少需要掃描一遍序列。

因為只能掃描一遍，所以先求出 a XOR b，再根據結果分類的方法就不適用了。

既然我們不能根據某一位分類，那我們能否對所有位進行分類呢？比如，int是32位，我們可以對每一位都分成兩類分別異或。

我們還要記錄每一位上1出現的次數，實際上，只需要記錄1出現奇數次還是偶數次就夠了。?

如果某一位上1出現奇數次，那么我們就知道 a 和 b 在此位上的比特不同。從而利用前面分類異或的結果就直接得出答案。

Python 代碼：

def?find_missing_2_numbers_v2(sequence,?n):
????"""?returns?the?missing?two?numbers?of?sequence,?which?is?supposed
????to?be?a?permutation?of?{1,..,n}?with?two?numbers?missing.
? ? An one-pass algorithm.
????"""
????xors?=?[[0?for?i?in?xrange(2)]?for?j?in?xrange(32)]
????counts?=?[0?for?i?in?xrange(32)]
????for?i?in?xrange(1,?n?+?1):
????????for?k?in?xrange(32):
????????????t?=?1?&?(i?>>?k)
????????????xors[k][t]?^=?i
????????????counts[k]?^=?t
????for?e?in?sequence:
????????for?k?in?xrange(32):
????????????t?=?1?&?(e?>>?k)
????????????xors[k][t]?^=?e
????????????counts[k]?^=?t
????a,?b?=?0,?0
????for?k?in?xrange(32):
????????if?counts[k]:
????????????a,?b?=?xors[k][0],?xors[k][1]
????????????break

? ??return?a,?b?

?

擴展問題三：如果有三個數字丟失了呢？

其實上面的方法稍加修改就可以解決此問，具體實現留給讀者。有道類似題目http://yzfy.org/dis/listpost.php?tid=1009?可以用來測試你的算法~

轉載于:https://www.cnblogs.com/shilcare/archive/2012/04/24/2468336.html

總結

以上是生活随笔為你收集整理的寻找丢失的数字（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。