题目描述
- 一个整数数组里除两个数字外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。比如{2,3,5,3,2,7},则两个只出现一次的数字为5和7.
解题思路
- 假设数组中只出现一次的两个数字为A和B。
- 一个数字异或自己的结果是0。依次将该数组进行异或,则得的到的结果即为为A和B异或的结果,因为其他成对出现的数字都抵消了。
- 由于A和B不同,所以A和B异或的结果肯定不为0。找出异或结果中第一个为1的位置,记为第n位。
- 以第n位是不是1为标准将原数组分为两个数组。这样A和B肯定在不同的数组里,并且相同的数字肯定在一个数组里。
- 对两个数组里的数字以此进行异或,得到的值即为A和B。
代码
int[] findNumbersAppersOnce(int[] arr){
if (arr == null || arr.length <= 1) {
return null;
}
// 对数组进行异或
int result = 0;
for (int i = 0; i < arr.length; i++) {
result = result ^ arr[i];
}
if (result == 0) {
return null;
}
// 找出第一个bit是1的位置
int flag = 1;
int flagIndex = 0;
while (flag != 0){
if ((flag & result) >= 1) {
break;
}
flag = flag << 1;
flagIndex ++;
}
// 分成两个数组进行异或
int numA = 0;
int numB = 0;
for (int i = 0; i < arr.length; i ++) {
if ((arr[i] >> flagIndex & 1) == 1 ) {
numA = numA ^ arr[i];
} else {
numB = numB ^ arr[i];
}
}
return new int[]{numA, numB};
}