九章算法-面试题总结 - Backyard of LixinZhang
有2n+1个数，其中2n个数两两成对，1个数落单，找出这个数。要求O(n)的时间复杂度，O(1)的空间复杂度。
进阶问题：如果有2n+2个数，其中有2个数落单，该怎么办？
分析
初阶：将2n+1个数异或起来，相同的数会抵消，异或的答案就是要找的数。
进阶：假设两个不同的数是a和b，并且a!=b，将2n+2个数异或起来就会得到c=a xor b，并且c不等于0。因此在c的二进制位中找到一个为1的位，可推断在这位上a和b分别为0和1，因此将2n+2个数分为该位位0的组和该位为1的组，两组中各自会包含2n'+1个数和2n''+1个数，用初阶的算法即可解决。
Read full article from 九章算法-面试题总结 - Backyard of LixinZhang
No comments:
Post a Comment