剑指offer面试题40 数组中只出现一次的数字

考察点

异或运算，与运算

知识点

题目

分析
本题目要求数组中只出现一次的俩个数字，并且要求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);}
}