設計一個可以確定缺失整數的分而治之算法

Question

給定一個數組A，按照某種順序包含所有k位非負整數中的一個，但找到具有以下約束的缺失整數：

你被允許做的只有兩件事與這些整數之一：

1. 獲得其第i位的值
2. 彼此交換它們在陣列中

例如：如果k爲3，則數組將包含除0和7之外的所有整數，其任務是查找缺少的整數。

Answer 1

你應該檢查每個比特（例如，如果k = 3，需要檢查所有的3個位）都存在2^k-1個倍0 & 1.

如果確定的你列出的列表不變（只有一個數字缺失並且沒有重複） - 確保它總是成立 - 那麼你可以簡單地只檢查一個，任意位保存上述條件。

例如，假設不變量成立，k = 3，並且您有列表[0-7]，不包括6. 對於列表中的每個數字，獲取它的第一個位（最低有效位）並執行以下：

if bit value = 0 then zeroValues++;
if bit value = 1 then oneValues++;

zeroValues應等於oneValues兩者應該等於2^k-1，在這種情況下，4

編輯：重讀你的問題，你看整個numbe河爲了找到您正在查找的整數值，只需執行所有位的過程。對於你做的每一點，你都會發現缺失0值或1值。缺少的值是結果整數中的位值。對所有位執行此操作將查找整數的整個位表示形式。

Answer 2

提示：你能找出缺失的數字是偶數還是奇數？

Answer 3

對於一個完全不同的方法提示，你可以排序數組？