无羡的博客
0%

位运算通解 只出现一次的数字

Posted on Edited on In

136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

1
2
示例 1:输入: [2,2,1] 输出: 1
示例 2:输入: [4,1,2,1,2] 输出: 4

假设没有时间复杂度和空间复杂度的要求，该题有很多种解法：哈希表 排序等
但是在线性时间复杂度和常数空间复杂度的限制条件下只有位运算的方法

位运算的基本内容

简单来说
位操作包括：

  • ~ 取反（NOT）
  • | 按位或（OR）
  • ^ 按位异或（XOR）
  • & 按位与（AND）
  • 移位 (移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。)
    • 算术移位
    • 逻辑移位
      这里简单解释下
      1
      2
      3
      4
      5
      6
      a = 21           (1 0 1 0 1)
      b = 11           (0 1 0 1 1)
      c = ~a = -22     (0 1 0 1 0)
      d = a | b = 31   (1 1 1 1 1)
      e = a ^ b = 30   (1 1 1 1 0)
      f = a & b = 1    (0 0 0 0 1)

秒杀与难度增大

这道题便用到了异或运算的两个重要特性：交换律，两相同数异或结果为零
即a^b^a = a^a^b = 0 ^ b = b
所以该题的解法为，将该数组的所有元素进行异或运算：

1
2
3
res = 0
for num in nums: res = res ^ num
return res

我们再看看这道题的后续 137. 只出现一次的数字 II 题目描述为：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

1
2
示例 1:输入: [2,2,3,2] 输出: 3
示例 2:输入: [0,1,0,1,0,1,99] 输出: 99

使用掩码

这题想要达到的效果是，在运算的过程中是0->1->2->0
这里要使用两个掩码Mask： Maskone和Masktwo。
假设有一个数为x,那么则有如下规律：

1
2
3
4
0 ^ x = x,
x ^ x = 0；
x & ~x = 0,
x & ~0 =x;

答案为

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = seen_twice = 0
        for num in nums:
            seen_once = ~seen_twice & (seen_once ^ num)
            seen_twice = ~seen_once & (seen_twice ^ num)
        return seen_once

那么就是很好解释上面的代码了。一开始a = 0, b = 0;

  1. x第一次出现后，a = (a ^ x) & ~b的结果为 a = x, b = (b ^ x) & ~a的结果为此时因为a = x了，所以b = 0。
  2. x第二次出现：a = (a ^ x) & ~b, a = (x ^ x) & ~0, a = 0; b = (b ^ x) & ~a 化简， b = (0 ^ x) & ~0 ,b = x;
  3. x第三次出现：a = (a ^ x) & ~b， a = (0 ^ x) & ~x ,a = 0; b = (b ^ x) & ~a 化简， b = (x ^ x) & ~0 , b = 0;所以出现三次同一个数，a和b最终都变回了0.
  4. 只出现一次的数，按照上面x第一次出现的规律可知a = x, b = 0;因此最后返回a.

最后的开胃小菜

260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

1
示例 :输入: [1,2,1,3,2,5] 输出: [3,5]

注意：
结果输出的顺序并不重要，对于上面的例子，[5, 3]也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
最后一题相对第二题比较简单，但是仍然需要一定的技巧：

  1. 按照第一题的方法获得 a^b，for num in nums: res = res ^ num
  2. 使用res将整个数组区分成为两个部分：
  3. 使用第一步的方法获取其中一个值
    简化代码如下图所示
    1
    2
    3
    4
    5
    6
    7
    # 假设数组为 [0, 0, 1, 1, 2, 3]
    bitmask = 2 ^ 3 = 1 # 1 0 ^ 1 1 = 0 1
    # res为一的最后一位为第一位，所以不同的两个数中必有一个数的第一位为一
    diff = bitmask & (-bitmask) = 1 # 0 1
    # 将数组分成两部分
    for num in nums:
    	if num & diff:x ^= num