《编程之美》快速找出故障机器

摘要：我们来看一道编程之美的题目，题目内容如下假设一台机器仅储存一份标号为的记录是小于亿的整数，假设每份数据保存两个备份，这样就有两台机器储存了同样的数据。

我们来看一道《编程之美》的题目，题目内容如下：
假设一台机器仅储存一份标号为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 machineIdList = new ArrayList<>();

        if (scanner.hasNext()){
            String input = scanner.nextLine();
            String[] machineList = input.split(",",0);
            for (int i=0;i machineIdList,int length) {
        HashMap hashMap = new HashMap<>();

        for (int i=0;i 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 machineIdList = new ArrayList<>();

        if (scanner.hasNext()){
            String input = scanner.nextLine();
            String[] machineList = input.split(",",0);
            for (int i=0;i machineIdList,int length) {
        HashSet hashSet = new HashSet<>();

        for (int i=0;i
诚然，上面的代码已经可以解决题目中提到的三个问题。但是，由于第二个问题的特殊性，我们可以用其他更巧妙的方式解答。先看第二个问题，“如果已经知道只有一台机器死机”，也就意味着在整个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 machineIdList = new ArrayList<>();

        if (scanner.hasNext()){
            String input = scanner.nextLine();
            String[] machineList = input.split(",",0);
            for (int i=0;i machineIdList,int length) {
        int result = 0;

        for (int i=0;i
遍历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)。