思路
相同的数异或为0,数字与0异或为其本身。
如果数组中只出现一次的数字仅一个,将数组的所有元素异或就可以得到单独的那个数字。
题目中特地提到只出现一次的数字有两个,所以需要先将数组拆分成两个,每个子数组里分配一个出现了一次的数字,然后分别异或即为答案:
- 将数组内所有数字进行异或,因为其他数字都出现了两次,所以结果为两个只出现一次数字的异或。
- 两个不同的数字异或结果中,肯定至少有一位等于1,可以用来区分这两个数字,并且可以根据该位为0或1将数组分组。
- 将两个子数组所有元素异或,可以找出答案的两个数。
时间复杂度O(n),空间复杂度O(1)。
代码
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length < 2) return ;
int tmp = array[0];
for(int i = 1; i < array.length; i++) {
tmp ^= array[i];
}
int flag = 1;
while((flag & tmp) == 0) {
flag <<= 1;
}
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; i++) {
if((flag & array[i]) == 0) {
num1[0] ^= array[i];
} else {
num2[0] ^= array[i];
}
}
}
}