找出 1..100 中缺失的整数

figure out which integer is missing

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

你有一个数组，包含集合 $\{1,2,3,\ldots,100\}$ 中的 99 个互不相同的整数。如何写程序找出缺失的那个整数？

You have an array that contains 99 distinct integers from the set 1,2,3,..., 100. How would you write a program to figure out which integer is missing?

解析

两种常见做法（都为 $O(n)$ 时间、 $O(1)$ 额外空间）：

方法 1：求和

总和应为

1+2+\cdots+100=\frac{100\cdot 101}{2}=5050.

缺失数 $=5050-\sum\text{(数组元素)}$ 。

方法 2：按位异或

利用 $a\oplus a=0$ 、 $0\oplus a=a$ 。计算

(1\oplus 2\oplus\cdots\oplus 100)\oplus (\text{数组所有元素异或}),

成对抵消后剩下的就是缺失数。