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

作者: 望月从良 | 来源:发表于2018-08-24 17:23 被阅读0次

给定一个集合:

屏幕快照 2018-08-22 下午5.19.35.png
它包含n个元素，每个元素都是一个数字，对于另一个集合A,它所有的元素都来自集合Z，现在已知的是，A中的集合相比于Z,它缺失了其中一个元素，同时有一个元素从复了两次，假设A中，元素

屏幕快照 2018-08-22 下午5.24.03.png

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

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

接着我们将Z中的每个元素都取平方，然后把所有元素加总，然后A中每个元素也取平方，也把所有元素加总，然后再将两者相减，于是就有sum( $z^2$ ) - sum( $A^2$ ) = ${x_n}^2$ - ${x_i}^2$ = ( $x_n$ - $x_i$ )( $x_n$ + $x_i$ )=S。由于前面我们已经算出了( $x_n$ - $x_i$ )= $S_1$ ，于是我们可以用S除以 $S_1$ 得到两者之和，也就是( $x_n$ + $x_i$ )= $S_2$ 。由此我们就得到了两个变量的方程，于是就可以把他们分别解出来， $x_n$ =( $S_1$ + $S_2$ )/2， $x_i$ =( $S_2$ - $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,然后随机选取两个元素作为重复元素和遗失元素，将两个元素输出，然后调用前面实现的算法去寻找这两个元素，代码运行结果如下：

屏幕快照 2018-08-22 下午6.10.08.png

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

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

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

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

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

这里写图片描述

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java 杂谈

数据结构和算法分析