共计 3549 个字符，预计需要花费 9 分钟才能阅读完成。
我们来看一道《编程之美》的题目，题目内容如下：
假设一台机器仅储存一份标号为 ID 的记录（ID 是小于 10 亿的整数），假设每份数据保存两个备份，这样就有两台机器储存了同样的数据。
1、在某个时间，如果得到一个数据文件 ID 的列表，是否能够快速地找出这个表中仅出现一次的 ID？
2、如果已经知道只有一台机器死机（也就是说只有一个备份丢失）？
3、如果有两台机器死机呢？
先看第一个问题，我们可以用常见的去重算法解答：遍历整个列表，用一个数组（或者 map）保存每个 ID 出现的次数，最后次数为 1 的 ID 即为这张表中仅出现一次的 ID。根据这个思路，我们可以写出下面的代码：
package algorith.machine;
import java.util.*;
public class Machine3 {public static void main(String[] args){Scanner scanner = new Scanner(System.in);
ArrayList<Integer> machineIdList = new ArrayList<>();
if (scanner.hasNext()){String input = scanner.nextLine();
String[] machineList = input.split(",",0);
for (int i=0;i<machineList.length;i++){machineIdList.add(Integer.parseInt(machineList[i]));
}
findBrokenMachine(machineIdList,machineIdList.size());
}
}
public static void findBrokenMachine(ArrayList<Integer> machineIdList,int length) {HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i=0;i<length;i++){if (hashMap.containsKey(machineIdList.get(i))){int value = hashMap.get(machineIdList.get(i));
hashMap.put(machineIdList.get(i),++value);
}else {hashMap.put(machineIdList.get(i),1);
}
}
for (Map.Entry<Integer,Integer> entry : hashMap.entrySet()){if (entry.getValue() == 1)
System.out.println(entry.getKey());
}
}
}
上述代码是用 hashMap 结构体实现的，如果用数组实现，可以用列表的 ID 值作为索引。由于 ID 的取值可能比较大（0~10 亿），而且完全随机，分配的数组空间更大，所以用 hashmap 存储较好。上述算法的空间复杂度为 O(N)，时间复杂度也为 O(N)。
有没有更高效的代码呢？
从题干中我们可以得知，这份 ID 列表最多只有两个重复的 ID。基于这个，我们可以考虑用 hashSet 存储数据，如果有重复的键值，则将 ID 从 hashSet 中移除，最终得到的 hashSet 就是只出现一次的 ID 列表。这个算法的空间复杂度在最好的情况下可以达到 O(1)，最坏的情况下仍然是 O(N)。代码如下：
package algorith.machine;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Machine1 {public static void main(String[] args){Scanner scanner = new Scanner(System.in);
ArrayList<Integer> machineIdList = new ArrayList<>();
if (scanner.hasNext()){String input = scanner.nextLine();
String[] machineList = input.split(",",0);
for (int i=0;i<machineList.length;i++){machineIdList.add(Integer.parseInt(machineList[i]));
}
findBrokenMachine(machineIdList,machineIdList.size());
}
}
public static void findBrokenMachine(ArrayList<Integer> machineIdList,int length) {HashSet<Integer> hashSet = new HashSet<>();
for (int i=0;i<length;i++){if (hashSet.contains(machineIdList.get(i))){hashSet.remove(machineIdList.get(i));
}else {hashSet.add(machineIdList.get(i));
}
}
System.out.println(hashSet);
}
}
诚然，上面的代码已经可以解决题目中提到的三个问题。但是，由于第二个问题的特殊性，我们可以用其他更巧妙的方式解答。先看第二个问题，“如果已经知道只有一台机器死机”，也就意味着在整个 ID 列表里，有且仅有一个 ID 出现过一次，其他 ID 均出现两次 ，在这里，我们可以用异或运算符的特性（ 每个数与它自身异或，结果为 0 ）设计一个空间复杂度仅为 O(1)的算法，程序如下所示：
package algorith.machine;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Machine2 {public static void main(String[] args){Scanner scanner = new Scanner(System.in);
ArrayList<Integer> machineIdList = new ArrayList<>();
if (scanner.hasNext()){String input = scanner.nextLine();
String[] machineList = input.split(",",0);
for (int i=0;i<machineList.length;i++){machineIdList.add(Integer.parseInt(machineList[i]));
}
findBrokenMachine(machineIdList,machineIdList.size());
}
}
public static void findBrokenMachine(ArrayList<Integer> machineIdList,int length) {
int result = 0;
for (int i=0;i<length;i++){result = result ^ machineIdList.get(i);
}
System.out.println(result);
}
}
遍历 ID 列表，将所有 ID 进行异或和，最后得到的结果就是仅出现过一次的 ID，用一个变量存储结果即可，大大降低空间复杂度。
第三个问题稍微有点复杂。两台机器死机，也就是说 ID 列表丢失了两个 ID，假设这两个 ID 分别为 A 和 B，所有 ID 异或运算的结果则为 A^B，无法正确区分出两个 ID 的值。对此，作者给出了两个方法求解：
- 分类讨论法
如果 A^B = 0，说明丢失的时同一份数据的两个备份，这时可以通过求和的方式得到 A 和 B，即：
A = B = ((所有 ID 之和 - 所有正常工作的 ID 之和)/2)如果 A^B != 0，那么在 A 和 B 的某一位上(假设为 i)，必定有 0 和 1 两个不同的取值，我们可以把所有 ID 分成两类，一类在 i 位上取值为 1，另一类在 i 位上取值为 0。然后遍历列表，用两个变量计算两类 ID 的异或和，最终得到的就是 A 和 B 的值。算法的时间复杂度为 O(2N)，空间复杂度为 O(1)。
- 预设“不变量”法
预先计算并保存好所有 ID 的求和 X，然后将所有剩下的 ID 相加，结果为 Y；
预先计算并保存好所有 ID 的平方和 S，然后计算剩下的 ID 的平方和，结果为 K。
用 A 和 B 代表丢失的 ID，则有：
A + B = X - Y
A^2 - B^2 = S - K根据以上两条公式，即可求解 A 和 B 的值，算法的时间复杂度为 O(2N)，空间复杂度为 O(1)。
