算法刷题Day5: BM52 数组中只出现一次的两个数字

描述：
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求：空间复杂度 O(1)，时间复杂度O(n)。

题目传送门 is here

思路：

方法一：最简单的思路就是使用字典记录每个数的出现次数，最后再遍历一遍字典出现次数为1的数。（空间复杂度 O(n)，时间复杂度O(n)。空间复杂度不满足题目条件。）

:)小妙招：使用字典的mydict[key] = mydict.get(key, 0)函数可以轻松将字典不存在的值设置为初始值0。

方法二：还是要用一个字典记录，但是如果出现第二次就remove掉，因此最后字典就只剩下出现一次的数值。（空间复杂度 O(n)，时间复杂度O(n)。空间复杂度不满足题目条件。）

基础知识： 使用mydict.get(key)获取key值，无就会返回None。

方法三：利用 异或 和 与 运算。

假设只出现一次的数为a，b。 大体思路分为三个步骤：
步骤一：
整个数组的数都异或一遍，最终的值为c = a^b。
步骤二：
打住！先花30秒思考如何利用c来得出a和b？
…1s…
…2s…
…3s…
.
.
…30s… okk 想到了吗？反正我没想到。[尬住哈]

答案：还记得异或特点是不同为1吗，a, b 两个不同的数异或出来，肯定会有至少某一位数是1。对吧。
上栗子！ 100 ^ 110 = 010 中间那位不一样 001 ^ 100 = 101 头尾两位不一样。 所以我们可以利用c 中为1的那一位，用来区分出 a 和 b。
具体做法就是，找为1的那一位，将整个数组分成两组数，一组含a和重复数， 另一组含b和重复数。 至此橘事已定。
步骤三：
最后梅开二度，再来一遍异或。分别对这两组数进行异或运算，最终得出一组异或值为a, 另一组的异或值为b。

回忆那死去的数学：
异或特点就是：两个相同的数异或结果为0，a ^ a = 0 ，相互抵消掉了。一个数异或0结果不变。 b ^ 0 = b
因此1 ^ 1 ^ 4 = 4
与操作特点：相同为1，不同为0，可以区分某个位上是0还是1。举个栗子：使用001分别与上000, 001, 010, 011 可以将一组数区分成000、010 和 001,011两组数，这两组数的特点是最后一位不相同。

代码：

#from typing import List
class Solution:# 方法一： count每个数的次数def FindNumsAppearOnce1(self , nums: List[int]) -> List[int]:# write code herecnt = {}for item in nums:cnt[item] = cnt.get(item, 0) + 1print(cnt)result = []for k ,v in cnt.items():if v == 1:result.append(k)return sorted(result)# 方法二：出现过就removedef FindNumsAppearOnce2(self , nums: List[int]) -> List[int]:# write code herecnt = {}for item in nums:if cnt.get(item) == None:cnt[item] = 1else:del cnt[item]result = []for k,_ in cnt.items():result.append(k)return sorted(result)# 方法三：使用异或def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:# 步骤一：全部异或一遍tmp = nums[0]for i in range(1,len(nums)):tmp = tmp ^ nums[i]print(tmp)# 步骤二：得出只有两个数得异或之后，从低位开始选择，第一个为1的那位，可以对这两个数进行分组group_num = 1while group_num & tmp == 0:group_num = group_num << 1print(bin(group_num))# 步骤三：进行分组group1 ,group2 = 0,0list1 ,list2 = [],[] # 这两个list只是拿来看看分组情况,最后[1,4,1,6] 会分成 [1,4,1] [6]for item in nums:if item & group_num == 0:list1.append(item)group1 = group1^item    # 对组1的数进行异或else:list2.append(item)group2 = group2^item    # 对组2的数进行异或print("group: ",list1, list2)if group1 > group2:return [group2, group1]else:return [group1, group2]#so = Solution()
#exp1 = [1,4,1,6]
#print(so.FindNumsAppearOnce(exp1))

昨天做的题，今天写个博客梳理一下。方法三里面考到的数学知识已经忘了，复习起来花了不少时间。本来用方法一和方法二就能通过了，觉得方法三没必要了。但是仔细一看空间复杂度，居然是O(1) ，那方法一、二的空间复杂度是O(n)，老不达标了。 牛客网放我过了，但是比赛或者面试的oj就没有那么仁慈了。因此还是要重视起时间复杂度和空间复杂度。有一位比赛大佬和我说，有时候呢，可以从这个时间复杂度还有数组的规模来判断用的是什么解法。比如时间复杂度为1s，数组长度>10^9次方。那肯定只能遍历一遍数组了，于是乎两层for循环那肯定过不了的。