算法刷题-位运算

2021-10-25 137

leetcode

前菜

异或的性质

两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。运算的逻辑是

如果同一位的数字相同则为 0，不同则为 1

异或的规律

任何数和本身异或则为 0
任何数和 0 异或是本身
异或满足交换律。即 a ^ b ^ c ，等价于 a ^ c ^ b

只出现一次的数字 1
题目大意是除了一个数字出现一次，其他都出现了两次，让我们找到出现一次的数。我们执行一次全员异或即可。

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    single_number = 0
    for num in nums:
        single_number ^= num
    return single_number

只出现一次的数字 2
题目大意是除了一个数字出现一次，其他都出现了三次，让我们找到出现一次的数。灵活运用位运算是本题的关键

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    res = 0
    for i in range(32):
        cnt = 0  # 记录当前 bit 有多少个1
        bit = 1 &lt;&lt; i  # 记录当前要操作的 bit
        for num in nums:
            if num & bit != 0:
                cnt += 1
        if cnt % 3 != 0:
            # 不等于0说明唯一出现的数字在这个 bit 上是1
            res |= bit

    return res - 2 ** 32 if res > 2 ** 31 - 1 else res

为什么 Python 最后需要对返回值进行判断？

如果不这么做的话测试用例是 [-2,-2,1,1,-3,1,-3,-3,-4,-2] 的时候，就会输出 4294967292。其原因在于 Python 是动态类型语言，在这种情况下其会将符号位置的 1 看成了值，而不是当作符号 “负数”。这是不对的。正确答案应该是 - 4，-4 的二进制码是 1111...100，就变成 2^32-4=4294967292，解决办法就是减去 2 ** 32 。

之所以这样不会有问题的原因还在于题目限定的数组范围不会超过 2 ** 32

错误的集合(就是本题)
和上面的 137. 只出现一次的数字2 思路一样。

这题没有限制空间复杂度，因此直接 hashmap 存储一下没问题。不多说了，我们来看一种空间复杂度 O(1)O(1) 的解法。

我们和 137. 只出现一次的数字2 思路基本一样，我直接复用了代码。

这里我们的思路是，将 nums 的所有索引提取出一个数组 idx，那么由 idx 和 nums 组成的数组构成 singleNumbers 的输入，其输出是唯二不同的两个数。

但是我们不知道哪个是缺失的，哪个是重复的，因此我们需要重新进行一次遍历，判断出哪个是缺失的，哪个是重复的。

class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
    ret = 0  # 所有数字异或的结果
    a = 0
    b = 0
    for n in nums:
        ret ^= n
    # 找到第一位不是0的
    h = 1
    while(ret & h == 0):
        h &lt;&lt;= 1
    for n in nums:
        # 根据该位是否为0将其分为两组
        if (h & n == 0):
            a ^= n
        else:
            b ^= n

    return [a, b]

def findErrorNums(self, nums: List[int]) -> List[int]:
    nums = [0] + nums
    idx = []
    for i in range(len(nums)):
        idx.append(i)
    a, b = self.singleNumbers(nums + idx)
    for num in nums:
        if a == num:
            return [a, b]
    return [b, a]

感谢 @云龙的提醒，上面的 h 计算过程甚至可以简化为 h = res ^ (res & (res-1))

实际上我这里只是为了重用之前的代码，让大家看出来套路。其实根本不需要什么 idx 数组。代码：

class Solution:

def findErrorNums(self, nums: List[int]) -> List[int]:
    ret = 0  # 所有数字异或的结果
    a = 0
    b = 0
    for n in nums:
        ret ^= n
    for i in range(1, len(nums) + 1):
        ret ^= i
    # 找到第一位不是0的
    h = 1
    while(ret & h == 0):
        h &lt;&lt;= 1
    for n in nums:
        # 根据该位是否为0将其分为两组
        if (h & n == 0):
            a ^= n
        else:
            b ^= n
    for n in range(1, len(nums) + 1):
        # 根据该位是否为0将其分为两组
        if (h & n == 0):
            a ^= n
        else:
            b ^= n
    for num in nums:
        if a == num:
            return [a, b]
        if b == num:
            return [b, a]

只出现一次的数字 3
题目大意是除了两个数字出现一次，其他都出现了两次，让我们找到这个两个数。

我们进行一次全员异或操作，得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个任何数和本身异或则为0，因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。
分组需要满足两个条件.

两个独特的的数字分成不同组
相同的数字分成相同组

这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢？

由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.

我们随便取一个，分组的依据就来了，就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。
这样肯定能保证 2. 相同的数字分成相同组，不同的数字会被分成不同组么。很明显当然可以，因此我们选择是 1，也就是
说两个独特的的数字在那一位一定是不同的，因此两个独特元素一定会被分成不同组。

class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
    ret = 0  # 所有数字异或的结果
    a = 0
    b = 0
    for n in nums:
        ret ^= n
    # 找到第一位不是0的
    h = 1
    while(ret & h == 0):
        h &lt;&lt;= 1
    for n in nums:
        # 根据该位是否为0将其分为两组
        if (h & n == 0):
            a ^= n
        else:
            b ^= n

    return [a, b]

作者：fe-lucifer
链接：https://leetcode-cn.com/problems/set-mismatch/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文导读