快速在组合中查找重复和遗失的元素

给定一个集合:

它包含n个元素，每个元素都是一个数字，对于另一个集合A,它所有的元素都来自集合Z，现在已知的是，A中的集合相比于Z,它缺失了其中一个元素，同时有一个元素从复了两次，假设A中，元素xn$x_n$，缺失了，然而xi$x_i$重复了两次，于是A的集合为：

请你给出一个算法，找出A中重复的元素和缺失的元素。要求算法的空间复杂度是O(1)，时间复杂度是O(n)。

这道题有两种解法，第一种想到不难，第二种很巧妙，要想到就很不容易了。我们先看第一种，我们先把Z中的元素加总，然后把集合A中的元素也加总，然后两种相减，也就是sum(Z) - sum(A),由于在A中xi$x_i$重复了两次，并且xn$x_n$缺失，于是有sum(Z) - sum(A) = xn$x_n$ - xi$x_i$ = S1$S_1$。

接着我们将Z中的每个元素都取平方，然后把所有元素加总，然后A中每个元素也取平方，也把所有元素加总，然后再将两者相减，于是就有sum(z2$z^2$) - sum(A2$A^2$) = xn2${x_n}^2$ - xi2${x_i}^2$= (xn$x_n$ - xi$x_i$)(xn$x_n$+xi$x_i$)=S。由于前面我们已经算出了(xn$x_n$ - xi$x_i$)=S1$S_1$，于是我们可以用S除以S1$S_1$得到两者之和，也就是(xn$x_n$+xi$x_i$)=S2$S_2$。由此我们就得到了两个变量的方程，于是就可以把他们分别解出来，xn$x_n$=(S1$S_1$+S2$S_2$)/2，xi$x_i$=(S2$S_2$-S1$S_1$)/2。

算法只需要遍历两个数组最多两次，没有用到新内存，因此算法复杂度为O(n)，空间复杂度为O(1)，我们看看相关代码实现：

public class FindDuplicateAndMissingElements {
    private int[] Z;
    private int[] A;
    private int missingElement = 0;
    private int duplicateElement = 0;
    public  FindDuplicateAndMissingElements(int[] Z, int [] A) {
        this.Z = Z;
        this.A = A;

        findElements();
    }

    private void findElements() {
        //先计算元素和
        int sumZ = 0, sumA = 0;
        int sumZ2 = 0, sumA2 = 0;
        for (int i = 0; i < Z.length; i++) {
            sumZ += Z[i];
            sumA += A[i];

            sumZ2 += Z[i]*Z[i];
            sumA2 += A[i]*A[i];
        }

        int s1 = sumZ - sumA;
        int s2 = (sumZ2 - sumA2)/s1;

        missingElement = (s1 + s2) /2;
        duplicateElement = (s2 - s1)/2;
    }

    public int getMissingElement() {
        return missingElement;
    }

    public int getDuplicateElement() {
        return duplicateElement;
    }
}

我们再看主入口处的代码：

import java.util.Arrays;
import java.util.Random;

public class Searching {
     public static void main(String[] args) {
        int n = 30;
        //构造一个含指定个元素的数组
        int[] Z = new int[n];
        int[] A = new int[n];
        HashSet<Integer> used = new HashSet<Integer>();

        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            int add = rand.nextInt(100);
            while (used.contains(add)) {
                add = rand.nextInt(100);
            }

            Z[i] = add;
            A[i] = Z[i];
            used.add(add);
        }
        //int[] Z = new int[]{1,2,3,4,5};
       // int[] A = new int [] {1,2,3,3,5};
        int missingPos = rand.nextInt(n-1);
        int duplicatePos = missingPos;
        while (duplicatePos == missingPos) {
            duplicatePos = rand.nextInt(n-1);
        }
        System.out.println("The missing element is: "+Z[missingPos] + " the duplicate element is " + Z[duplicatePos]);
        A[missingPos] = A[duplicatePos];

        FindDuplicateAndMissingElements fa = new FindDuplicateAndMissingElements(Z, A);
        System.out.println("missing element found by algorithm is " + fa.getMissingElement());
        System.out.println("duplicate element found by algorithm is " + fa.getDuplicateElement());
}

代码先构造一个含有30个元素的数组A和Z,然后随机选取两个元素作为重复元素和遗失元素，将两个元素输出，然后调用前面实现的算法去寻找这两个元素，代码运行结果如下：

从结果上看，我们的算法实现是正确的。接下来我们看看第二种比较巧妙的算法。第二种方法依赖于亦或运算，特别是同一个数自身做亦或等于0，同时亦或具有交换律，例如x1 xor x2 xor x1 = x1 or x1 xor x2 = 0 xor x2 = x2。我们如何使用亦或特性来查找重复和遗失的元素呢，具体步骤如下。

根据假设，在集合A中，元素xi$x_i$重复了两次，xn$x_n$遗失，那么我们先把集合A中的所有元素进行亦或运算，XOR(A)=x1$x_1$ xor x2$x_2$…xi$x_i$ xor xi$x_i$… xor xn−1$x_{n-1}$。然后我们把集合Z中所有元素也进行亦或运算，XOR(Z)=x1$x_1$ xor x2$x_2$…xi$x_i$… xor xn$x_n$。然后再把两个结果进行亦或运算XOR(A) xor XOR(Z) = (x1$x_1$ xor x2$x_2$…xi$x_i$ xor xi$x_i$… xor xn−1$x_{n-1}$) xor (x1$x_1$ xor x2$x_2$…xi$x_i$… xor xn$x_n$)，根据我们前面讲过的亦或性质有XOR(Z) xor XOR(A) = xi$x_i$ xor xn$x_n$。

由于xi$x_i$与xn$x_n$不相同，因此XOR(Z) xor XOR(A) = m != 0，也就是xi$x_i$与xn$x_n$做亦或后，所得结果的二进制形式上，在某一位一定是1，在这个二进制位上xi$x_i$与xn$x_n$不一样，要不然该位亦或后不可能得1，接着我们遍历集合Z,把所有在该二进制位上为1的元素拿出来形成一个新的集合C={xi1$x_{i1}$,xi2$x_{i2}$…xim$x_{im}$}，然后再遍历集合A，把所有该二进制位为1的元素拿出来形成集合D={xt1$x_{t1}$,xt2$x_{t2}$…xtm$x_{tm}$}，如果xi$x_i$的对应二进制位是1，那么集合C包含了一个xi$x_i$,集合D包含了两个xi$x_i$，除此之外其他元素都相同，于是XOR(C) xor XOR(D) = xi$x_i$，如果是xn$x_n$对应二进制位是1的话，那么集合C包含xn$x_n$，集合D不包含xn$x_n$，除此之外所有其他元素都相同，因此XOR(C) xor XOR(D) = xn$x_n$，无论如何我们只要把XOR(c) xor XOR(D)的结果在集合A中查找，如果它存在集合A中，那么它就是重复的元素xi$x_i$，如果不在集合A中，它就是遗失的元素xn$x_n$。

同理，我们只要在集合A和Z中分别找出对应二进制位为0的元素，然后才去与上面所说的相同步骤，我们就能查询到另一个对应元素，如果上面找到的是重复元素，那么我们这里就能找到遗失元素，如果上面找到的是遗失元素，我们这里找到的是重复元素。

由于算法只遍历集合A与Z,没有分配多余内存，因此算法时间复杂度是O(n)，空间复杂度是O(1)，我们看看相关代码实现：

  private void findElementByXor() {
        int xorA = 0, xorZ = 0;
        for (int i = 0; i < Z.length; i++) {
            xorA = xorA ^ A[i];
            xorZ = xorZ ^ Z[i];
        }

        int m = xorA ^ xorZ;
        int mark = 1;
        int i = 0;
        while (true) {
            mark = mark << i;
            if ((m & mark) != 0) {
                break;
            }
            i++;
        }

        //从A与Z中选出对应二进制位为1的元素进行亦或运算
        xorA = 0;
        xorZ = 0;

        int xorA0 = 0;
        int xorZ0 = 0;

        for (i = 0; i < Z.length; i++) {
            if ((A[i] & mark) != 0) {
                xorA = xorA ^ A[i];
            } else {
                xorA0 = xorA0 ^ A[i];
            }

            if ((Z[i] & mark) != 0) {
                xorZ = xorZ ^ Z[i];
            } else {
                xorZ0 = xorZ0 ^ Z[i];
            }
        }

        //得到遗失或重复的元素
        int t = xorA ^ xorZ;
        int k = xorA0 ^ xorZ0;

        boolean findInA = false;
        for (i = 0; i < A.length; i++) {
            if (t == A[i]) {
                findInA = true;
                break;
            }
        }

        if (findInA) {
            duplicateElement = t;
            missingElement = k;
        } else {
            duplicateElement = k;
            missingElement = t;
        }
    }

上面代码运行后，一样可以得到正确结果。方法2比方法1的优越之处在于，方法1在对元素求平方时，有可能会导致溢出，而方法2不会，因此方法2的鲁棒性比方法1要好很多。

更详细的讲解和代码调试演示过程，请点击链接

更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：