本文共 13050 字，大约阅读时间需要 43 分钟。

【基础不扎实的 同学们 先看 位运算系列，重点是LC645的思路5】

---

本题解析(2个1次，其他2次)

【思路】异或

要求时间复杂度是O(n)，空间复杂度是O(1)。则不能使用 哈希表和数组 计数，所以可以考虑 异或

1. 全员异或，得到a,b异或的几个 sums

2. 获得mask

   法1：

   mask = sums & (-sums)

   法2：

   mask=1	# 初始化mask=1while sums & mask == 0:	mask <<=1

   Q.什么是mask? mask干嘛用？

   比如 设置mask为1，则二进制为0001
   mask是一个二进制数，且其中只有一位是1，其他位全是0，比如0010，0100，1000
   mask用来表示我们用哪一位作为分组标准，比如 当mask = 0010，则 mask和num与&操作后，倒数第二位是0的数字分到一组，倒数第二位是1的分到另一组

3. 区分a,b，和每个数num异或，为0分一组，为1分一组

   根据 &是否为0 区分将两个数字分区，并分别求异或和

nums = [4,1,4,6]step1. 全员异或	sums = 1^6=001^110=111step2. 获得mask	   法1.mask = sums & (-sums) = 111 & 001 = 001	   法2.while+左移		   111&001 = 001 该题遇到001,就得到不为0的结果,可跳出循环，mask即为001		   否则继续判断 sums&010, &100 等step3. 区分a,b	   num=4	100&001=000		b=b^num=000^100=100	   num=1	001&001=001		a=a^num=000^001=001	   num=4	100&001=000		b=b^num=100^100=000	   num=6	110&001=000		b=b^num=000^110=110不管其他数分在那一组,总有两个,总能抵消为0,所以异或最终结果是剩下的那个数重点是将1和6分在不同组 即可更多细节参考LC645的【思路5】异或

class Solution:    def singleNumbers(self, nums):        a=b=sums=0        # 1.全员异或,异或和是a^b的结果        for num in nums:            sums ^= num        # 2.得到mask        mask = sums & (-sums)        # 3.区分a和b        for num in nums:            if num & mask:                a ^= num            else:                b ^= num        # print([a,b])        return [a,b]

<只出现一次的数 系列>位运算

本题和主站 260 是一样的. 除了这个，主站还有 136 和 137，645。 总共加起来本系列一共 四道题。四道题全部都是位运算的套路，如果你想练习位运算的话，不要错过~作者：fe-lucifer链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-a/来源：力扣（LeetCode）

基础知识

①. 异或a^b

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

②.异或运算

重点~ 切记！

x ^ 0 = x​ ， x ^ 1 = ~x

• 任何数和 本身异或则为 0
• 任何数和 0 异或 是 本身
• 异或 满足交换律。

  a ^ b ^ c ，等价于 a ^ c ^ b

③.与运算

重点~ 切记！

x & 0 = 0 ， x & 1 = x

1.LC136(1个1次，其他2次)

我们执行一次全员异或即可

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

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

====================================

2.LC137(1个1次，其他3次)

【思路1】数学解

将输入数组存储到 HashSet(不重复的数)，然后使用 HashSet 中数字和的三倍与数组之和比较。

3 x (a + b + c) - (a + a + a + b + b + b + c) = 2 c

class Solution:    def singleNumber(self, nums: List[int]) -> int:        return (3 * sum(set(nums)) - sum(nums)) // 2

• 时间复杂度：O(N)，遍历输入数组。
• 空间复杂度：O(N)，存储 N/3 个元素的集合。
  空间复杂度 不符合题设

【思路2】有限状态自动机

对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0, 1, 2 。

• 若输入二进制位 1 ，则状态按照以下顺序转换；
• 若输入二进制位 0 ，则状态不变。

0→1→2→0→⋯

由于二进制只能表示 0, 1。因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 two , one，则状态转换变为：

00→01→10→00→⋯

num是数组的每个值，不一定是1,0 emm ~ ~ 作者是拿0 1数写的特例，对大于1的数，我就很懵了~ 有点绕 求指点 ~

class Solution:    def singleNumber(self, nums: List[int]) -> int:        ones, twos = 0, 0        for num in nums:            ones = ones ^ num & ~twos            twos = twos ^ num & ~ones        return ones'''作者：jyd链接：https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/来源：力扣（LeetCode）'''

• 时间复杂度 O(N) ： 其中 N 位数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(32x3x2) = O(1)。
• 空间复杂度 O(1) ： 变量 ones , twos 使用常数大小的额外空间。

【思路3】位操作

<逐位考虑>

我们单独看二进制某一位，先不看单独的那个数，其他所有数字都出现了 3 次，所以那一位是 1 的个数一定是 3 的倍数。

如[2,2,3,2] ==》[10,10,11,10]，其中10₍₂₎有三个，则1有3个. 模3为0

再考虑这个出现一次的数，如果这一位是 1 ，那么这一位 1 的次数模 3 为 1 ，否则的话模 3 就是 0 。

其中11₍₂₎有1个，则1有1个. 模3为1

那么就很简单了，统计一下 这一位上 有多少个数 是 1 ，然后模 3 取余数，结果就是这个单独的数这一位上的值了。

遍历 32 位整数的每一位，就可以得到这个单独的数是多少了。

<推广到一般情况>

如果其他数都出现了 k 次，一个数出现了一次。那么：

• 如果 k 是偶数，还是把所有的数异或起来就行了。
• 如果 k 是奇数，那么统计每一位是 1 的个数，然后模 k 取余数 就能得到那个单独的数了。

上述这部分解析的作者：godweiyang

链接：https://leetcode-cn.com/problems/single-number-ii/solution/zi-dong-ji-wei-yun-suan-zui-xiang-xi-de-tui-dao-gu/

class Solution:    def singleNumber(self, nums: List[int]) -> int:        counts = [0] * 32        for num in nums:        	# 统计每个位上的 1的个数            for j in range(32):                counts[j] += num & 1                num >>= 1                        res, m = 0, 3        for i in range(32):        	# i从0开始,表示count从最后一位开始取模            res <<= 1            # res为0时,左移也无效,所以它针对的是有值的时候            res |= counts[31 - i] % m   # 得到 模3为1的数        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)'''作者：jyd链接：https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/来源：力扣（LeetCode）'''

实际上，只需要修改求余数值 m ，即可实现解决 除了一个数字以外，其余数字都出现 m 次 的通用问题

注：

• res |= counts[31 - i] % m # 得到 模3为1的数，别担心，它不会得到2，不用发愁它得到2怎么办，题目设定的是 除了一次，只有三次，即res只会得到 模3为0/1
• return res if counts[31] % m == 0 else ~(res^0xffffffff) # count[31]即左第一列，若为0，则res为正数；
  若为负，则res为负，要进行取反操作

• 时间复杂度 O(N) ： 其中 N 位数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(1)。
• 空间复杂度 O(1) ： 数组 counts 长度恒为 32 ，占用常数大小的额外空间。

【附：思路3打印版】

class Solution2:    def singleNumber(self, nums):        counts = [0] * 32        for num in nums:            print('num = ',num,end='\t')            			# 二进制数的打印            if num>=0:                print(bin(num)[2:].zfill(32))   # 正数的原码            else:                print(bin(num & 0xffffffff)[2:])# 负数的补码                			# 统计每个位上的 1的个数            for j in range(32):                # count是倒着存,第一位存最右边一位的 1的个数                counts[j] += num & 1    # 更新第 j 位                num >>= 1               # 第 j 位 --> 第 j + 1 位                # 比如2的二进制10,num先是0,右移        print('counts = ',counts)        res, m = 0, 3        for i in range(32):            res <<= 1            print('i = %d,原res=%d'%(i,res))            print('counts[%d] = %d'%(31 - i,counts[31 - i]))                        # i从0开始,表示count从最后一位开始取模            res |= counts[31 - i] % m   # 得到 模3为1的数            print('后res',res)            print()        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)s = Solution2()nums = [-2,-2,-3,-3,-3,5,-2]one = s.singleNumber(nums)print('只出现一次的是:',one)

打印个负数的看看

【附：思路3的简洁版】 这里的cnt在每次循环都会清空，记录每一位的1个数后，立即判断 模3的结果，不等0（即为1）就进行 或操作

class Solution:    def singleNumber(self, nums: List[int]) -> int:        res = 0        for i in range(32):            cnt = 0  # 记录当前 bit 有多少个1            bit = 1 << 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'''作者：fe-lucifer链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-a/来源：力扣（LeetCode）'''

【补充知识点】

• 计算机内存中一律用补码来表示整数：正数的补码 就等于它的原码，而负数的补码 按位取反再+1
• 对于一个负数 -x，它的二进制表示（补码）求法如下：

  1. 求出-x 的 相反数x 的原码 （-x=-10, x=10,x的原码：0000 1010）2. 对 x 的原码进行取反运算  （取反：1111 0101）3. 将取反运算的结果+1	     （+1 ：1111 0110）# https://blog.csdn.net/u012511672/article/details/51724272

• 二进制数的打印

  nums=[1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7]for num in nums:	if num>=0:    	print(num,'\t',bin(num)[2:].zfill(32))      	else:    	print(num,'\t',bin(num & 0xffffffff)[2:])

  
• 运算符优先级【从低到高】

  运算符优先级 【从低到高】

  1. Lambda （运算优先级最低）
  2. 逻辑运算符: or
  3. 逻辑运算符: and
  4. 逻辑运算符:not
  5. 成员测试: in, not in
  6. 同一性测试: is, is not
  7. 比较: <,<=,>,>=,!=,==
  8. 按位或: |。只有 0|0为0，其他情况为1
  9. 按位异或: ^。相同为0，相异为1
  10. 按位与: &。只有 1 &1 为1，其他情况为0。
  11. 移位: 左移<< , 右移>>（2的幂相关）
  12. 加法与减法: + ,-
  13. 乘法、除法与取余: *, / ,%
  14. 正负号: +x,-x （运算优先级最高）

惭愧~ 这道题啃了好久，都没太搞懂。关键是遗忘了位运算知识，回忆起来 到 灵活运用，是一个漫长的过程

参考链接：

3.LC645(1个0次，1个2次，其他1次)

【思路1】简洁解法

class Solution:    def findErrorNums(self, nums: List[int]) -> List[int]:        return [sum(nums)-sum(set(nums)), sum(range(1, len(nums)+1)) - sum(set(nums))]

sum(nums)-sum(set(nums)) 即复制的元素

.

range(1, len(nums)+1) 指的是【正常数组(升序 间隔1)中 本该存储的数】

sum(set(nums)) 使用set函数，错误数组的set集合 会比 正常数组的set集合 少一个数，这个数就是丢失的数

【思路2】暴力解法

1. 遍历 1 到 n 的所有数字
2. 在检查每个数字时 遍历整个 nums 数组，统计 每个该数字 在nums数组中出现的次数
3. 检查当前数字在 nums 中是否出现了两次，或者一次都没有出现
   使用 dup 和 missing 记录重复数字和缺失数字。

~ 超出时间限制 ~

class Solution:    def findErrorNums(self, nums):        dup=0        missing=0	# 初始化 什么值都可以        for i in range(1,len(nums)+1):	# 检查 1 到 n 的所有数字            count=0            for j in range(len(nums)):	# 遍历整个 nums 数组                if nums[j]==i:	# 统计次数                    count+=1            # print(i,count)            if count==2:	# 出现两次的 就是重复数字                dup=i            elif count==0: # 没出现的 就是缺失数字                missing=i            # print(dup,missing)        return dup,missings = Solution()nums = [1,2,2,4]      one = s.findErrorNums(nums)'''1 10 02 22 03 02 34 12 3'''

• 时间复杂度：O(n²)，在 1 到 n 的每个数字上，都需要遍历一次 nums。
• 空间复杂度：O(1)，使用恒定的额外空间。

【暴力解的优化版】

~ 还是超出时间限制 ~

class Solution:    def findErrorNums(self, nums: List[int]) -> List[int]:        dup=0        missing=0        for i in range(1,len(nums)+1):            count=0            for j in range(len(nums)):                if nums[j]==i:count+=1            if count==2:                dup=i            elif count==0:                 missing=i            if dup>0 and missing>0:                break        return dup,missing

• 时间复杂度：O(n²)， 在最坏的情况下，需要在 1 到 n 的每个数字上遍历一次 nums。
• 空间复杂度：O(1)，使用恒定的额外空间。

【思路3】哈希map

1.计数dic = collections.Counter(nums)

2.检查 1 到 n 的每个数字在 map 中出现次数： 如果一个数字的出现了两次，它就是重复数字dup； 如果一个数字在 map 中没有出现，它就是缺失数字missing。

class Solution:    def findErrorNums(self, nums: List[int]) -> List[int]:        dup=0        missing=0        dic = collections.Counter(nums)        for i in range(1,len(nums)+1):            if dic[i]==2:	# 出现了两次                dup = i            elif dic[i]==0: # 没有出现                missing = i        return dup,missing

dic = Counter({2: 2, 1: 1, 4: 1, 5: 1}) 就像数组那样读取

dic[1] = 1

dic[2] = 2

dic[3] = 0 # 不存在就为0

• 时间复杂度：O(n)，遍历 nums 需要时间 O(n)，在 map 中检查每个数字需要时间 O(n)。
• 空间复杂度：O(n)，map 最多需要存储 1 到 n 共 n 个数字。

【思路4】用数组计数

<一行代码 变成 三行代码>

用数组 cnt 代替 map，索引代表数字，cnt 存储每个数字出现的次数。 例如 cnt[i] 存储数字 i 出现的次数。 注：

• cnt 的长度应为 len(nums)+1，因为还有个cnt[0]，虽然我们不存什么
• for i in range(1,len(cnt)) 检查 这些数字出现次数，为2的是dup，为0的是missing。所以这里是 数组cnt 的长度

class Solution: # 数组    def findErrorNums(self, nums):        dup=0        missing=0        cnt = [0]*(len(nums)+1)        # 在数组 arr 中，索引代表数字，arr 存储每个数字出现的次数        for i in range(len(nums)):  # 0123            cnt[nums[i]] += 1        # print(cnt)        for i in range(1,len(cnt)):            if cnt[i]==2:                dup = i            elif cnt[i]==0:                missing = i            # print(dup,missing)        return dup,missing'''[0, 1, 2, 0, 1, 1]0 02 02 32 3'''

• 时间复杂度：O(n)，遍历 nums 需要时间 O(n)，在 map 中检查每个数字需要时间 O(n)。
• 空间复杂度：O(n)，数组 arrarr 最多需要存储 1 到 n 共 n 个数字的出现次数。

【思路5】异或 ☆☆☆

重复数字dup，缺失数字mis

step1. 将 原数组 和 辅助数组 所有元素(8个)进行异或

原数组		辅助数组（正常数组,无重复值,无缺值）1 001 		1 0012 010 		2 0102 010 		3 0114 100 		4 100

可知 dup的有3个，mis有1个

其余元素各2个。在异或运算中，成对出现的都会抵消为0

故最后的结果就是 dup^ mis。将其保存为sum，即 001

step2. 将 dup 和 mis 分开处理

对于sum而言，其中“1”所在的位置就是dup和mis不相同的位（必定是一个为‘0’，一个为‘1’）

这样的1有若干个，不妨将最靠右的1作为鉴别点，重新将上述8个元素分为两部分，则dup和mis在不同的两部分。

对于这个例子，我们按照第0位是否为1将它们分类，

假设对应位是‘0’为p0类，对应位是‘1’为p1类（粗体）。

p0类		p1类2 010		1 001 		2 010		1 001 		2 010		3 0114 100  			4 100

注：这里实现分类的方法是: 令 t = sum & (-sum)，然后将t与所有元素分别按位与，结果不为零则该元素此位为‘1’，否则为‘0’。

-sum是负数，sum=001，则按位取反 +1，得 -sum=111

则 t = sum & (-sum) = 001

step3. 两部分 分别将所有元素异或

p0类	p1类
有3个dup，其余元素成对出现	有1个mis，其余元素成对出现

对于这两部分，各自将自身所有元素按位异或^，发现结果正好一个是dup【即2】，一个是mis【即3】。

但此时我们还没把他们区分开

step4. 区分出哪个是dup和mis

将两个结果分别设为 p0 和 p1，任取一个，计算其在nums数组中出现的次数： 若为0，则此数为mis，另一个为dup；

若为2，则此数为dup，另一个为mis。

duck不必 计算次数！

存在就是dup，不存在就是mis

class Solution:    def findErrorNums(self, nums):        dup = mis = sums = part0 = part1 = 0        count = 0        # step1:将 原数组 和 辅助数组 所有元素(8个)进行异或        for i in range(len(nums)):  # 0 1 2 3            sums ^= (i+1)^nums[i]        # print(sums)        # step2+3:将 dup 和 mis 分两部分,分别将所有元素异或        t = sums & (-sums)        # print(t)        for i in range(1,len(nums)+1):   # 1 2 3 4            if t&i: # 与正常数组的异或，看分为 p0类 还是 p1类                part1 ^= i	# 非0 归为 p1类            else:                   part0 ^= i	# 为0 归为 p0类        for i in range(len(nums)):   # 1 2 2 4            if t&nums[i]: # 与原数组的异或，看分为 p0类 还是 p1类                part1 ^= nums[i]            else:                   part0 ^= nums[i]                # step4:区分出哪个是dup和mis        for i in range(len(nums)):            if nums[i]==part0:                # print(part0, part1)                return part0, part1        # print(part1, part0)        return part1, part0

这step2+3在干嘛？看下面：

'''step2+3 的具体展示'''t=001	# 与正常数组的异或，看分为 a0类 还是 a1类i=1		t&1=001		p1=p1^1=000^001=001		【1】	与结果非0,故存入p1i=2		t&2=000		p0=p0^2=000^010=010		【2】	与结果为0,故存入p0i=3		t&3=001		p1=p1^3=001^011=010		【1^3】	与结果非0,故存入p1i=4		t&4=000		p0=p0^4=010^100=110		【2^4】	与结果为0,故存入p0t=001	# 与原数组的异或，看分为 a0类 还是 a1类i=0	num[0]=1=001	t&num[0]=001	p1=p1^1=010^001=011	【1^3^1】剩3i=1 num[1]=2=010	t&num[1]=000	p0=p0^2=110^010=100	【2^4^2】剩4i=2 num[2]=2=010	t&num[2]=000	p0=p0^2=100^010=110	【2^4^2^2】剩4^2i=3 num[3]=4=100	t&num[3]=000	p0=p0^2=110^010=010	【2^4^2^2^4】剩2

• 时间复杂度：O(n)。遍历 n 个元素 5 次。

• 空间复杂度：O(1)。使用恒定的额外空间。

  参考 https://leetcode-cn.com/problems/set-mismatch/solution/cuo-wu-de-ji-he-by-leetcode/

【再举个栗子】

设输入nums=[1,2,2,3,5]原数组		辅助数组（正常数组,无重复值,无缺值）1 001 		1 0012 010 		2 0102 010 		3 0113 011 		4 1005 101       5 101sums = 2^4 = 010^100 = 110 -sums = 001+1 = 010t = sums & (-sums) = 110 & 010 = 010则根据第2位是否为0的 分类为0分p0类   为1分p1类p0类		p1类1 001       2 010		 		1 001       2 010		 		4 100       2 0105 101       3 0115 101       3 011a0类 全员异或得100=4a1类 全员异或得010=2输出[2,4]