考察点
异或运算,与运算
知识点
题目
分析
本题目要求数组中只出现一次的俩个数字,并且要求O(1)时间复杂度和空间复杂度。试想一下如果只有一个数字出现一次,那么针对全部元素做异或运算就可以了,因为相同元素异或为0。现在有俩个数字出现了一次,那么我们其实可以依据数字位的一些特性,我们可以首先异或全部元素,这个值肯定是这俩个只出现一次的数字的异或值,既然值不相同那么肯定从右起有一位元素是1,这是这俩个数字不相同的原因之一,我们可以再找出来到底是第几位元素,然后再次遍历数组,针对所有元素判断该位是否是1分别做异或运算即可
public class Forty{
public static void main(String[] args) {
int[] arr = {2,4,3,6,3,2,5,5};
getDifferentNum(arr);
}
public static void getDifferentNum(int[] arr) {
int num = 0;
for (int i = 0;i<arr.length;i++) {
num = num ^ arr[i];
}
//找到右起第一位不是0的
int cnt = 0;
int oneNum = 1;
while(oneNum > 0) {
if((num & oneNum) == 0) {
cnt++;
} else {
break;
}
oneNum = oneNum << 1;
}
int numA = 0;
int numB = 0;
for(int i = 0;i<arr.length;i++) {
oneNum = 1;
if(((oneNum << cnt) & arr[i]) == 0) {
numA = numA ^ arr[i];
} else {
numB = numB ^ arr[i];
}
}
System.out.println(numA);
System.out.println(numB);
}
}