題目
一個(gè)整型數(shù)組 nums 里除兩個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次咆耿。請寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字萨螺。要求時(shí)間復(fù)雜度是O(n)愧驱，空間復(fù)雜度是O(1)。
示例 1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
限制：
2 <= nums <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有吻商。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)糟红，非商業(yè)轉(zhuǎn)載請注明出處。
思路
首先看個(gè)簡單版柒爸，數(shù)組中只出現(xiàn)一次的數(shù)字事扭，其他都出現(xiàn)了兩次。
直接把所有的數(shù)字異或起來就得到答案了求橄，原因是哪些出現(xiàn)兩次的數(shù)字和自己異或之后就變成了0.
這一題是升級版，出現(xiàn)了兩個(gè)數(shù)字条霜，全部異或下來的話啃匿，等于兩個(gè)數(shù)的異或蛆楞。
那么我們可以想辦法把這兩個(gè)數(shù)字分成兩組夹厌，一組是num1和一些一對對的數(shù)字矛纹，另一組是num2和一對對的數(shù)字。怎么分開的話孩等，用全部的數(shù)字異或的結(jié)果采够，得到的結(jié)果，找到里面包含1的位數(shù)蹬癌，和每個(gè)數(shù)相與的話,就能進(jìn)行分組。（因?yàn)檫@是兩個(gè)不同的數(shù)異或的結(jié)果隅要，異或就是在位上不同則為1２角濉）
代碼
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
result = 0
for i in nums:
result ^= i
h = 1
while result&h == 0:
h <<= 1
num1, num2 = 0,0
for num in nums:
if num&h == 0:
num1 ^= num
else:
num2 ^= num
return [num1,num2]
