博客

传说浙大有一个面试题是要快速找到1到N中缺少的一个数字，有一个很经典的做法是把N-1个数字加和，减去1到N的和，但是当N非常很大的时候，复杂度为O(Nlog(N^2)/32) = O(Nlog(N)/16)，和会达到2logN的bit位。

我偶然想到了一个方法，设f(n) = 1 xor 2 xor … xor n

f(n) =

n , n % 4 == 0

1 , n % 4 == 1

n +1 , n % 4 == 2

0 , n % 4 == 3

设输入的n-1个数字的异或和为s, 那么所求答案就为 f(n) – s. 复杂度为O(Nlog(N)/32)，即只使用log(N)长度的bit位。

不知道有没有更加优秀的方法，请各位大佬指点。