快速找出故障机器（微软面试题）

题目：假设一个机器仅储存一个标号为ID的记录（假设其小于10E的整数），假设每份数据保存两个备份，这样就有两个机器储存了同样的数据。 1、在某时刻，如果得到一个数据文件ID的列表，如何能够快速找出这个表中仅出现一次的ID？（相当于只有一个故障机器） 2、如果两个丢失呢？ 解法之一： 利用数学的“不变量”概念，这些数据的ID总值是不变的，我们只需要故障前把每一台机器存储的ID值进行求和运算，当发现有机器死机了，就可以把之前求得的总和减去剩余的数量的机器ID之和，所得的差即是发生故障的ID。这是针对已知仅有一台机器数据出问题。此时的时间复杂度为O（N），空间复杂度为O（1）。 当有两台机器出故障时，假设这两台机器的数据ID分别为x，y。我们可以根据上面的方法求得x+y的和，而这里有两个未知数，我们得再构建一个等式，由数学知识可知，两个未知数可由两个等式解得。故再根据ID乘积之和总量不变，除去剩余ID值之乘积，所得为x*y的值。这样两个未知数可以求得。 时间复杂度同样为O（N），空间复杂度为O（1） 如果ID值比较大，数量比较多，避免乘积发生溢出，可以构造平方和。