位运算
我这里总结了几道位运算的题目分享给大家,分别是 136 和 137, 260 和 645, 总共加起来四道题。 四道题全部都是位运算的套路,如果你想练习位运算的话,不要错过哦~~

前菜

开始之前我们先了解下异或,后面会用到。
  1. 1.
    异或的性质
两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算,得出的数字。 运算的逻辑是果同一位的数字相同则为 0,不同则为 1
  1. 1.
    异或的规律
  2. 2.
    任何数和本身异或则为0
  3. 3.
    任何数和 0 异或是本身
  4. 4.
    异或运算满足交换律,即:
a ^ b ^ c = a ^ c ^ b
OK,我们来看下这三道题吧。

136. 只出现一次的数字 1

题目大意是除了一个数字出现一次,其他都出现了两次,让我们找到出现一次的数。我们执行一次全员异或即可。
1
class Solution:
2
def singleNumber(self, nums: List[int]) -> int:
3
single_number = 0
4
for num in nums:
5
single_number ^= num
6
return single_number
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为数组长度。
  • 空间复杂度:$O(1)$

137. 只出现一次的数字 2

题目大意是除了一个数字出现一次,其他都出现了三次,让我们找到出现一次的数。 灵活运用位运算是本题的关键。
Python3:
1
class Solution:
2
def singleNumber(self, nums: List[int]) -> int:
3
res = 0
4
for i in range(32):
5
cnt = 0 # 记录当前 bit 有多少个1
6
bit = 1 << i # 记录当前要操作的 bit
7
for num in nums:
8
if num & bit != 0:
9
cnt += 1
10
if cnt % 3 != 0:
11
# 不等于0说明唯一出现的数字在这个 bit 上是1
12
res |= bit
13
14
return res - 2 ** 32 if res > 2 ** 31 - 1 else res
Copied!
  • 为什么 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
JavaScript:
1
var singleNumber = function (nums) {
2
let res = 0;
3
for (let i = 0; i < 32; i++) {
4
let cnt = 0;
5
let bit = 1 << i;
6
for (let j = 0; j < nums.length; j++) {
7
if (nums[j] & bit) cnt++;
8
}
9
if (cnt % 3 != 0) res = res | bit;
10
}
11
return res;
12
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为数组长度。
  • 空间复杂度:$O(1)$

645. 错误的集合

和上面的137. 只出现一次的数字2思路一样。这题没有限制空间复杂度,因此直接 hashmap 存储一下没问题。 不多说了,我们来看一种空间复杂度$O(1)$的解法。
由于和137. 只出现一次的数字2思路基本一样,我直接复用了代码。具体思路是,将 nums 的所有索引提取出一个数组 idx,那么由 idx 和 nums 组成的数组构成 singleNumbers 的输入,其输出是唯二不同的两个数。
但是我们不知道哪个是缺失的,哪个是重复的,因此我们需要重新进行一次遍历,判断出哪个是缺失的,哪个是重复的。
1
class Solution:
2
def singleNumbers(self, nums: List[int]) -> List[int]:
3
ret = 0 # 所有数字异或的结果
4
a = 0
5
b = 0
6
for n in nums:
7
ret ^= n
8
# 找到第一位不是0的
9
h = 1
10
while(ret & h == 0):
11
h <<= 1
12
for n in nums:
13
# 根据该位是否为0将其分为两组
14
if (h & n == 0):
15
a ^= n
16
else:
17
b ^= n
18
19
return [a, b]
20
21
def findErrorNums(self, nums: List[int]) -> List[int]:
22
nums = [0] + nums
23
idx = []
24
for i in range(len(nums)):
25
idx.append(i)
26
a, b = self.singleNumbers(nums + idx)
27
for num in nums:
28
if a == num:
29
return [a, b]
30
return [b, a]
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

260. 只出现一次的数字 3

题目大意是除了两个数字出现一次,其他都出现了两次,让我们找到这个两个数。
我们进行一次全员异或操作,得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个任何数和本身异或则为0, 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。 分组需要满足两个条件.
  1. 1.
    两个独特的的数字分成不同组
  2. 2.
    相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢?
由于异或的性质是,同一位相同则为 0,不同则为 1. 我们将所有数字异或的结果一定不是 0,也就是说至少有一位是 1.
我们随便取一个, 分组的依据就来了, 就是你取的那一位是 0 分成 1 组,那一位是 1 的分成一组。 这样肯定能保证2. 相同的数字分成相同组, 不同的数字会被分成不同组么。 很明显当然可以, 因此我们选择是 1,也就是 说两个独特的的数字在那一位一定是不同的,因此两个独特元素一定会被分成不同组。
1
class Solution:
2
def singleNumbers(self, nums: List[int]) -> List[int]:
3
ret = 0 # 所有数字异或的结果
4
a = 0
5
b = 0
6
for n in nums:
7
ret ^= n
8
# 找到第一位不是0的
9
h = 1
10
while(ret & h == 0):
11
h <<= 1
12
for n in nums:
13
# 根据该位是否为0将其分为两组
14
if (h & n == 0):
15
a ^= n
16
else:
17
b ^= n
18
19
return [a, b]
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为数组长度。
  • 空间复杂度:$O(1)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。