乐趣区

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

jiezi

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

退出移动版