找数组中两个不同的数字也可以用位运算？｜刷题打卡

在数组中找不同的数字可以说是一道很基础的题目，寻常来说只需要遍历一次就行，一次不行，那就两次，总是可以的。

但是如果加上了限制条件呢？

原题链接：剑指 Offer 56 - I. 数组中数字出现的次数 （提示：本题是剑指Offer系列题目，有会员权限，有可能无法打开链接）

一、先看题

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

示例：

示例2：

提示：

• 2<=nums.length<=105

二、整理思路

题目很简单，只有三句话。 老规矩，拿到题目先理清思路。

第一步：

确认输入输出：

输入：一个数组；输出：两个只出现一次的数字组成的数组。

第二步

怎么处理输入才能得到输出？

根据我们平常生活中的思维，一眼扫过去，直接就能找到两个孤零零的数字，可这是数组短的情况下。如果说这个数组很长呢？长到填满A4纸的那种？

这时候我们就会想到，拿笔来，左手指着一个，右手找到一样的就划掉他们。诶，没错！这种思路在算法中也可以实现，那就是遍历数组，然后找到一样的数的时候，就把他们从数组中删掉，这样最后剩下的不就是两个单身狗了吗？！

可是，这时候就要看题干了，题干里有这么一句话：要求时间复杂度是O(n)，空间复杂度是O(1)。

这么一来，就不能简单粗暴的用两个遍历嵌套来对比了，所以我们可以选择另外一种方式来处理。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function (nums) {
    let res=[]
    for(let i=0;i<nums.length;i++){
        //因为每个数最多出现两次
        //那么只要删除后面出现的那个数
        //就可以避免重复遍历了
        let idx = res.indexOf(nums[i])
        if(idx<0){
            res.splice(idx,1)
        }else{
            res.push(nums[i])
        }
    }
    return res
}

简单粗暴的遍历法，提交之后，速度垫底。。。 不过这在意料之中，做算法嘛，先解出来才是王道。

既然这样不行，那么再对他优化一下呢？

我们知道除了两个数，其他都是重复了两次的，那么我们如果先将他们排序，再进行处理，那岂不是就可以直接跳过删除这个环节，直接跳到下一个不同的数上进行判断了吗？

这样一来，我们需要处理的数直接减半。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function (nums) {
    let res=[]
    let srtNums = nums.sort((a,b)=>{return a-b})
    for(let i=0;i<nums.length;i++){
        if(nums[i]!=nums[i+1]){
            res.push(nums[i])
            //如果已经找到了两个数，剩下的就不用再处理了
            if(res.length>=2){ break}
        }else{
            //因为同样的数排在一起，所以直接跳过
            i++
        }
    }
    return res
}

经过这一番剪枝和优化，我们的用时不再垫底，来到了三分之一的底部。

根据以往经验，即使测试用例有所不同，用时的比例也只有10%以内的波动浮动，也就是说，这个算法的优化空间依然巨大！

那么到底是什么方法呢？苦思很久都没有想到办法，看了题解，不得不说，这真是妙蛙种子回老家，妙到姥姥家了。先上代码，大家可以思考一下：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
    let res=0
    //取得两个不同的数的异或值
    for(let i=0;i<nums.length;i++){
        res^=nums[i]
    }
    //取得最低的不同位，为了方便理解，在这称mask为辨别码
    let mask=1;
    while((mask&res)==0){
        mask<<=1
    }
    let a=0,b=0;
    for(let i=0;i<nums.length;i++){
        //利用辨别码对数组进行分组
        //从而将找两个数转为找数组中不同的一个数的问题
        if((mask&nums[i])==0){
            a^=nums[i]
        }else{
            b^=nums[i]
        }
    }
    return [a,b]
}

大家如果有做过那道找出数组中只出现过一次的数的算法题，应该都会对位运算有些印象。

简单来说，就是两个相同的数进行异或运算之后，会变为0，而0和任意数异或都为他本身，即5^5==0;5^0==5。

根据这个思路，只要我们将数组中的数分为两组，每组只包含一个单独出现的数，那么就可以将其子数组中所有的数进行异或运算，就能得到这个数。

这个思路的难点，就在于怎么将不同的这两个数，刚好每个子数组分一个呢？

如果说，大家异或运用比较熟练的话，会想到奇偶数分组的运算，即进行&1操作，即通过判断数字的最后一位二进制是否为1，来进行分组，如果是奇数，那么&1之后必定为1，偶数则为0。

同样的思路，我们只要通过一个类似于1的功能的数，来对数字进行分组，那么岂不是就能将这两个数刚好分开？？

由于这两个数不同，因此不管怎么样，他们至少有一位二进制不同，我们只要找到最低位的这个二进制数，就可以将所有的数通过&操作来对他们进行分组了。

至此理清了思路，速度的确快了不少，更重要的是，对位运算的操作又熟悉了一分，不得不感慨位运算的奇特性。

三、总结

对于一道看似简单的题目，如果我们要深究下去，可能都还有很大的提升空间，但是优化一般来说都是耗时耗力的，减少损耗的唯一方法就是提高我们对编程基础的掌握，对原理了解的越深，我们才能做得更好。

一起加油吧！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情