剑指40.数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路

根据题意，如果要求空间复杂度为O(1)，则不能使用哈希表了。这道题考察的是位运算。

Tips：如果数组中只有一个数字只出现一次，从头到尾异或每个数字，那么最终的结果刚好是那个只出现一次的数字。原因：异或运算满足交换律，那些成对出现两次的数字全部在异或中抵消了。

那么对于本题来说，数组中有两个数字只出现一次，如果能够将数组分为两部分，两部分中都只有一个数字只出现一次，那么就可以解决该问题了。此时，我们从头到尾异或每个数字，最终得到的结果是两个只出现一次的数字的异或结果。由于这两个数字不同，那么在这个结果数字的二进制表示中至少有1位是1。我们把结果中从右往左第一个为1的位置记为第 n 位，因为这是两个只出现一次的数字的异或结果，所以这两个数字在第 n 位上的数字一定是1和0.

现在我们以第 n 位是不是1为标准把原数组中的数字分成两部分，第一个子数组中每个数字第 n 位都是1，而第二个子数组每个数字第 n 位都是0. 因为两个相同的数字的任意一位都是相同的，因此出现了两次的数字一定会被分配到同一个子数组。

最后，对两个子数组从头到尾异或，就可以得到这两个数了。

解法

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    // 使用HashMap
    /*public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length < 2)
            return;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num : array){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        boolean flag = true;
        for (int key : map.keySet()){
            if (map.get(key) == 1){
                if (flag){
                    num1[0] = key;
                    flag = false;
                }else{
                    num2[0] = key;
                }
            }
        }
    }*/
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length < 2)
            return;
        int ans = 0;
        // 第一个循环找到只出现一次的那两个数字的异或结果
        for (int num : array)
            ans ^= num;
        // 从右往左找到第一个不为0的位置对应的数，用来分割数组。
        int indexOf1 = 1;
        while ((ans & indexOf1) == 0)
            indexOf1 <<= 1;
        num1[0] = 0;
        num2[0] = 0;
        for (int x : array){
            if ((x & indexOf1) == 0){
                num1[0] ^= x;
            }else{
                num2[0] ^= x;
            }
        }
    }
}

收获

当一个数字出现两次（或者偶数次）时，用异或^ 可以进行消除。

参考：

【Java】剑指offer(56-1) 数组中只出现一次的两个数字