剑指Offer-面试题56-I-数组中数字出现的次数

2020-05-05

题目描述

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

示例1：

1 2	输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例2：

1 2	输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]

限制：2 <= nums <= 10000

思路

由于数组中只有两个数字是不重复的，设这两个不重复的数字为x、y，于是将数组的所有数进行异或，最终得到的结果是设为k = x ^ y（因为相同数进行异或的结果=0）。
例：

数组为：[4,1,4,6]
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6 = 7(111)
6的二进制：110
1的二进制：001
1 ^ 6 = 7(111)

但是我们无法通过7(111)去获得1(001)和6(110)。我们想到了分组，于是需要一个方法来将1(001)和6(110)分到不同的组中。
按照什么规则来对1(001)和6(110)进行分组可以将它们分到不同的组中？

可以通过1(001)和6(110)的低位第一位不同的值来进行分组。（在这个例子中，低位第一位不相同的位就是从右往左的第一位）。
我们可以设置一个变量mask，根据最终数组异或的结果是k = 7(111)，从右往左找第一个是1的位（即代表x和y在这个位上的值是不一样的）。
mask的初始值=1(001)，通过k & mask判断结果是否=0，若=0，证明这个位上的值=1，否则需要将mask左移1位，即mask << 1 = 2(010)，接着寻找。

通过上面的方法得到了分组规则mask的值

遍历数组，通过nums[i] & mask的结果=0/1来分成两组
重复的数字必将被分到同一组，x和y必将被分到不同组
将这两个组的所有数进行异或，重复的数字抵消，最后就剩下了两个结果，这两个结果就是x和y

代码

class Solution{
    public int[] singleNumbers(int[] nums){
        int k = 0;  //数组异或结果
        //遍历数组，对数组中的所有数进行异或
        for(int i=0;i<nums.length;i++){
            k ^= nums[i];
        }
        int mask = 1;   //初始化mask=1
        //从低位找第一个值=1的位
        while((k & mask) == 0){
            mask = mask << 1;
        }
        int[] result = new int[2];  //结果
        //遍历数组
        for(int i=0;i<nums.length;i++){
            //将&mask=0的数分到一组，并异或
            if((nums[i] & mask) == 0){
                result[0] ^= nums[i];
            }
            //将&mask=1的数分到一组，并异或
            else{
                result[1] ^= nusm[i];
            }
        }
        return result;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。