摘要：我們來看一道編程之美的題目，題目內容如下假設一臺機器僅儲存一份標號為的記錄是小于億的整數(shù)，假設每份數(shù)據(jù)保存兩個備份，這樣就有兩臺機器儲存了同樣的數(shù)據(jù)。

我們來看一道《編程之美》的題目，題目內容如下：
假設一臺機器僅儲存一份標號為ID的記錄（ID是小于10億的整數(shù)），假設每份數(shù)據(jù)保存兩個備份，這樣就有兩臺機器儲存了同樣的數(shù)據(jù)。
1、在某個時間，如果得到一個數(shù)據(jù)文件ID的列表，是否能夠快速地找出這個表中僅出現(xiàn)一次的ID？
2、如果已經(jīng)知道只有一臺機器死機（也就是說只有一個備份丟失）？
3、如果有兩臺機器死機呢？

先看第一個問題，我們可以用常見的去重算法解答：遍歷整個列表，用一個數(shù)組（或者map）保存每個ID出現(xiàn)的次數(shù)，最后次數(shù)為1的ID即為這張表中僅出現(xiàn)一次的ID。根據(jù)這個思路，我們可以寫出下面的代碼：

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結構體實現(xiàn)的，如果用數(shù)組實現(xiàn)，可以用列表的ID值作為索引。由于ID的取值可能比較大（0~10億），而且完全隨機，分配的數(shù)組空間更大，所以用hashmap存儲較好。上述算法的空間復雜度為O(N)，時間復雜度也為O(N)。

有沒有更高效的代碼呢？

從題干中我們可以得知，這份ID列表最多只有兩個重復的ID。基于這個，我們可以考慮用hashSet存儲數(shù)據(jù)，如果有重復的鍵值，則將ID從hashSet中移除，最終得到的hashSet就是只出現(xiàn)一次的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
誠然，上面的代碼已經(jīng)可以解決題目中提到的三個問題。但是，由于第二個問題的特殊性，我們可以用其他更巧妙的方式解答。先看第二個問題，“如果已經(jīng)知道只有一臺機器死機”，也就意味著在整個ID列表里，有且僅有一個ID出現(xiàn)過一次，其他ID均出現(xiàn)兩次，在這里，我們可以用異或運算符的特性（每個數(shù)與它自身異或，結果為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進行異或和，最后得到的結果就是僅出現(xiàn)過一次的ID，用一個變量存儲結果即可，大大降低空間復雜度。
第三個問題稍微有點復雜。兩臺機器死機，也就是說ID列表丟失了兩個ID，假設這兩個ID分別為A和B，所有ID異或運算的結果則為A^B，無法正確區(qū)分出兩個ID的值。對此，作者給出了兩個方法求解：
分類討論法
如果A^B = 0，說明丟失的時同一份數(shù)據(jù)的兩個備份，這時可以通過求和的方式得到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
根據(jù)以上兩條公式，即可求解A和B的值，算法的時間復雜度為O(2N)，空間復雜度為O(1)。