1 问题定义
题目：假设一个机器只存储一个标号为ID的记录，假设每份数据保存2个备份，这样就有2个机器存储了相同的数据。其中ID是小于10亿的整数
问题1在某个时间，如果得到一个数据文件ID的列表。是否能够快速的找到这个表中仅出现一次的ID?
问题2如果有两台机器死机呢（假设同一个数据的俩个备份不会同时丢失，即列表中缺少的是两个不等的ID）？
扩展题 如果所有的机子都有三个备份，也就是说同一ID的机子有三台。而且同时又有三台机子死机，还能用上面的方法解决吗？如果有N台备份，又同时有N台机器死机呢？
2 分析与求解
这个问题可以转化为：有很多的ID，其中只有一个ID出现的次数为2，其它正常ID出现的次数都等于2，问如何找到这个次数为1的ID。
10亿= 230，即一个ID可以用一个int（4个字节32bit）类型存放。
解法一：简单法
直接遍历列表，利用一个数组记下每个ID出现的次数，遍历完毕后，出现次数等于1的ID就是我们想要的结果。时间复杂度O(N)，空间复杂度O(N)。
优化：使用动态数组，遍历列表，如果访问的列表中的数已在数组中存在则删除，反之添加到数组。遍历完列表，数组中的数即为结果。时间复杂度O(N)，空间复杂度最好O(1)，最坏情况仍为O(N)。
显然简单方法可以回答问题1、2。稍加修改即可回答扩展问题，即找出出现次数小于3 (N)的即为坏死的机器。在优化中当某台机器出现的次数等于3（N）时从数组中删除，遍历完成剩下的即是坏死的机器。
解法二：位运算
机器ID的最大值为30bit，即一个ID可以用一个int来存储。令X为任意的int数，则X^X = 0，X^0 = X，其中^为位运算异或。因此对于问题1我们可以将所有的机器ID做异或运算，最后的结果为坏掉机器的ID，问题1得解。时间复杂度O(N)，空间复杂度O(N)，仅仅一个int变量即可。
对于问题2，若两台坏掉的机器ID不同，则所有机器ID异或的结果不为0。对于异或结果中的某位1，有且仅有1个数中在对应位为1。如此便可以根据此位是否为1将所有的机器ID分为两组，两组分别求异或的值，即可找出坏掉机器的ID。时间复杂度O(N)，但需要遍历两遍列表；空间复杂度O(1)。
但对于扩展问题就无能为力啦。
解法三：解方程
令SUM为所有机器ID的总和。SUM最大值为230*230= 260，即需要60bit = 8byte的存储空间，一个long可以搞定。
对于问题1，将所有机器的ID相加得sum’，因为坏掉一台机器，所以有sum’ <SUM且SUM – sum’即为坏掉机器的ID。
对于问题2，SUM-sum’为两台坏掉的机器的ID之和，只需找到第二个方程便可以计算出两台机器的ID。第二个方程可以为所有ID的累乘，但最大ID为10亿，所有数的累乘将相当可观，需要3010亿bit的存储空间存储累乘的积。第二个方程也可以为机器ID的平方和且最大值为290，即需要90bit = 12byte的存储空间。
对于扩展问题，思路相同，补充第三个方程为机器ID的三次方之和……直到补足N个方程，解方程即可。
若不考虑解方程的时间，时间复杂度O(N)，空间复杂度O(1)。
缺点：随着相同ID机器数的增加方程的求解也变得复杂。
三种方法的比较
对于问题1以及问题2中坏掉的机器ID不同的情况，方法2较理想。问题2中两台机器ID相同时，解法3较好，解法2无能为力。但问题规模增大时，反而方法1更方便解决，因为方法2失效，方法3中方程的求解变得越来越复杂。
参考：编程之美