一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是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.length <= 10000
思路:
- 相等的数异或为0,除a外其他数字都有两个一样的则异或结果为a
- 将a、b分为两组,且相同的两个数要在同一组,每组异或则可得到a、b
- 除a、b外其他数字都有两个一样的 则异或结果ret 为a、b异或结果,找到ab异或结果ret为1的位作为分组依据即可
java
class Solution {
public int[] singleNumbers(int[] nums) {
int ret=0;
for(int n:nums){
ret^=n;
}
int div=1;
while((div&ret)==0){
div<<=1;
}
int a=0,b=0;
for(int n:nums){
if((div&n)==0){
a^=n;
}
else{
b^=n;
}
}
return new int[]{a,b};
}
}
python
class Solution(object):
def singleNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ret,div,a,b=0,1,0,0
for n in nums:
ret^=n
while div&ret==0:
div<<=1
for n in nums:
if div&n==0:
a^=n
else:
b^=n
return [a,b]