算法

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素出现两次。找出只出现一次的元素。

示例

输入: [2,2,3] 输出: 3

思想

使用按位异或。异或：如果a、b两个值不相同，则异或结果为1。 如果a、b两个值相同，异或结果为0。

public static void main(String[] args) {
	int a [] = new int []{2,2,3};
	int temp = 0;
	for (int i = 0; i < a.length; i++) {
		temp ^= a[i];
	}
	System.out.println(temp);
}

加强

上述数组中有两个数出现一次，求这两个数。

示例

输入: [2, 2, 6, 4, 5, 5] 输出: 4, 6

思想

先将所有数按位异或，得到temp，找到temp中二进制位为1的下标，通过这个下标将所用数分为两个数组，分别异或可以得到两个值。

若有两个数都只出现了一次，若将所有数进行按位异或后，所得到的数中，若按照上述划分，必然可以将这两个数分到不同的数组中

代码

public static void main(String[] args) {
	int a [] = new int []{2, 2, 6, 4, 5, 5};
	int temp = 0;
	int max = 0;
	for (int i = 0; i < a.length; i++) {
		temp ^= a[i];
		if (max < a[i]) {
			max = a[i];
		}
	}

	int maxLength = Integer.toBinaryString(max).length();
	String tempString = Integer.toBinaryString(temp);
	StringBuilder sb = new StringBuilder(maxLength);
	for (int i = 0; i < maxLength-tempString.length(); i++) {
		sb.append("0");
	}
	sb.append(tempString);
	int index = sb.length() - 1;
	for (; index >= 0; index--) {
		if(sb.charAt(index) == '1') {
			break;
		}
	}
	int temp1 = 0;
	int temp2 = 0;
	for (int i = 0; i < a.length; i++) {
		String aiBinary = Integer.toBinaryString(a[i]);
		if(aiBinary.length()>index && aiBinary.charAt(aiBinary.length()-index-1) == '1') {
			temp1 ^= a[i];
		} else {
			temp2 ^= a[i];
		}
	}
	System.out.print(temp1 + ", " + temp2);
}