题目描述
leetcode 260
算法流程
1.求数组的异或和为sum
2.找出sum对应二进制数中为1的任意一位,假设该位为pos
3.若pos=1,那么必然是该位置上有奇数个0和奇数个1,因为数组总数是偶数
4.将pos=0的进行异或得到一个值,将pos=1的进行异或得到一个值;这是问题就转到leetcode 136,pos=0的在一个数组,pos=1的在一个数组
代码
public int[] singleNumber(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++)
sum^=nums[i];
int pos=0;
for(int bit=0;bit<32;bit++)
if((sum>>bit&1)==1)
{
pos=bit;
break;
}
int s1=0;
int s2=0;
for(int i=0;i<nums.length;i++)
if((nums[i]>>pos&1)==1)
s1^=nums[i];
else
s2^=nums[i];
return new int[]{s1,s2};
}