algorithm - O(n) 算法，找到缺失的整数

Question

数组 A 包含 [0, n-1] 范围内的 n-1 个唯一整数，也就是说，该范围内有一个数字不在 A 中。设计一个 O(n) 算法来找到该数字。除了数组 A 本身之外，只允许使用 O(1) 额外空间。

这个问题需要一些帮助，

Answer 1

1. 对数组求和。
2. 使用算术级数公式计算预期总和

给定这些值：一个是0 + 1 + 2 + ... + n-1，另一个是实际元素的总和 - 想想它们之间的区别，一个有什么，另一个没有。确保你知道它，答案是微不足道的。

编辑：（理论评论）：
注意sum(array)需要2*log_2(max(arr))位。因此，如果您的元素都是 32 位整数，那么您最多需要 64 位来表示总和。
从纯粹的理论方法 - 它不是O(1)。但是，您可以使用数组本身（它包含更多2*log_2(max(arr)) 位）来存储总和。

Answer 2

使用一个用 -1 初始化的附加tmp变量，然后使用tmpas position对数组进行排序n：

function find_missing(array)
begin
  tmp := -1
  i := 0;
  while i<length(array)
    if (array[i] = -1) or (array[i] = i) then
      // either on a cell with the right number or 
      // a candiate for the missing number, just go on
      i := i + 1
    else if array[i] = n then
      // use tmp as the nth cell
      array[i]=tmp
      tmp=n
    else
      // swap the value of the current cell with the value
      // of the cell were the value i should be
      swap(array, i, array[i])
    end if
  end while
end

-1 应该指向丢失的数字。

Answer 3

这是另一种方法：

1. 用 0 设置一个临时变量 Number
2. 对于数组中的每个元素，设置 Number = Number XOR element
3. 对于每个数字 M，M > N 和 M < 2**(ceil(log2(N)) 设置 Number = Number XOR M
4. 缺少号码是号码