Skip to content

Latest commit

 

History

History
200 lines (144 loc) · 6.83 KB

bit.md

File metadata and controls

200 lines (144 loc) · 6.83 KB

位运算

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

前菜

开始之前我们先了解下异或，后面会用到。

  1. 异或的性质

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

  1. 异或的规律

  • 任何数和本身异或则为0

  • 任何数和 0 异或是本身

  1. 异或运算满足交换律，即：

a ^ b ^ c = a ^ c ^ b

OK，我们来看下这三道题吧。

136. 只出现一次的数字 1

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

classSolution: defsingleNumber(self, nums: List[int]) ->int: single_number=0fornuminnums: single_number^=numreturnsingle_number

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为数组长度。
  • 空间复杂度：$O(1)$

137. 只出现一次的数字 2

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

Python3:

classSolution: defsingleNumber(self, nums: List[int]) ->int: res=0foriinrange(32): cnt=0# 记录当前 bit 有多少个1bit=1<<i# 记录当前要操作的 bitfornuminnums: ifnum&bit!=0: cnt+=1ifcnt%3!=0: # 不等于0说明唯一出现的数字在这个 bit 上是1res|=bitreturnres-2**32ifres>2**31-1elseres
  • 为什么 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:

varsingleNumber=function(nums){letres=0;for(leti=0;i<32;i++){letcnt=0;letbit=1<<i;for(letj=0;j<nums.length;j++){if(nums[j]&bit)cnt++;}if(cnt%3!=0)res=res|bit;}returnres;};

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为数组长度。
  • 空间复杂度：$O(1)$

645. 错误的集合

和上面的137. 只出现一次的数字2思路一样。这题没有限制空间复杂度，因此直接 hashmap 存储一下没问题。 不多说了，我们来看一种空间复杂度$O(1)$的解法。

由于和137. 只出现一次的数字2思路基本一样，我直接复用了代码。具体思路是，将 nums 的所有索引提取出一个数组 idx，那么由 idx 和 nums 组成的数组构成 singleNumbers 的输入，其输出是唯二不同的两个数。

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

classSolution: defsingleNumbers(self, nums: List[int]) ->List[int]: ret=0# 所有数字异或的结果a=0b=0forninnums: ret^=n# 找到第一位不是0的h=1while(ret&h==0): h<<=1forninnums: # 根据该位是否为0将其分为两组if (h&n==0): a^=nelse: b^=nreturn [a, b] deffindErrorNums(self, nums: List[int]) ->List[int]: nums= [0] +numsidx= [] foriinrange(len(nums)): idx.append(i) a, b=self.singleNumbers(nums+idx) fornuminnums: ifa==num: return [a, b] return [b, a]

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

260. 只出现一次的数字 3

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

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

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

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

  2. 相同的数字分成相同组

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

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

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

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

classSolution: defsingleNumbers(self, nums: List[int]) ->List[int]: ret=0# 所有数字异或的结果a=0b=0forninnums: ret^=n# 找到第一位不是0的h=1while(ret&h==0): h<<=1forninnums: # 根据该位是否为0将其分为两组if (h&n==0): a^=nelse: b^=nreturn [a, b]

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为数组长度。
  • 空间复杂度：$O(1)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

close