Leetcode 260. 只出现一次的数字 III -详解

你的名字 2022-03-19 05:07 186阅读 0赞

### 题目 ###

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
    
    示例 :
    
    输入: [1,2,1,3,2,5]
    输出: [3,5]
    注意：
    
    结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
    你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

### 解法1 ###

老样子，先来一种简单的办法，新开1个dict、1个list ，list存放结果，dict用来去重。O(n) 时间复杂度，但是不符合 `常数空间复杂度` 。解法如下：

dict = { }
            r = []
            for i in nums:
                if i in dict :
                    del  dict[i]
                else:
                    dict[i] = 0
    
            for j in dict:
                r.append(j)
    
            return r

### 解法2 ###

第2中解法是参考了评论区 @mbinary 的算法，先上解法：

xor = 0
            for i in nums:
                xor ^=i
            n = len(bin(xor))-3
            a,b=0,0
            for i in nums:
                if i>>n&1:
                    a^=i
                else:
                    b^=i
            return b,a

可以看到，这种解法，符合O(n) 空间、时间复杂度。  
思路如下：首先，把整个nums 异或一遍，得到 一个 `xor` 值，为了理解方便， 拿 `[2,2,3,3,5,1]`为例子，xor 为 4 ，根据推导式算出 n =2 ，下面遍历出来，`a = a ^ 5 =5 ;b= b ^ 2 ^ 2 ^ 3 ^ 3 ^ 1 = 1` 得到 `a=5;b=1`

那么这里如何得到推导式 `n = len(bin(xor))-3` 的？再看1个例子相信你就明白了：  
这次拿 `[2,2,1,1,5,4]`为例子，xor 为 1 ，根据推导式算出 n =0 ，下面遍历出来，`a = a ^ 5 ^ 1 ^ 1 =5 ;b= b ^ 2 ^ 2 ^ 4 = 4` 得到 `a=5;b=4`

> n 其实是右移之后最低为是否为1 的右移长度，也就是参与xor运算的两个不同数的 对应xor的最高1 位上 肯定一个是1一个是0

而你肯定也发现了，这两个例子中，`[2,2,3,3,5,1]` 与 `[2,2,1,1,5,4]` 重复的位其实是不重要的，`[2,2,3,3,5,1]`中的 `2和3`会被分配到 b的运算中，而 `[2,2,1,1,5,4]` 中的 `2和1`会被分配到 a 的运算中。

实际上，这些数会被xor 清空掉，留下不同的 a,b 。相当于： `[x1,x2 ,y1,y2 ,a,b]` 。 所以重要的是一个区分a,b 的条件，也就是这种解法中的 通过 a xor b 的结果，得到的右移区分 ab的条件。