如何找出数组中只出现一次的数字

问题描述： 一个整型数组里除了一个数字之外， 其他数字都出现了两次。找出这个只出现1 次的数字。要求时间复杂度是O（n）， 空间复杂度是O（1）。

用异或满足交换律来做这道题目：

System.out.println(4 ^ 7);// 3
System.out.println(4 ^ 7 ^ 4);// 7
System.out.println(4 ^ 7 ^ 4 ^ 7);// 0

当两个数相同的时候，异或操作得到0

故解此题的代码为：

	public static void method(int[] a) {
		int res = a[0];
		for (int i = 1; i < a.length; i++) {
			res ^= a[i];
		}
		System.out.println("只出现一次的数为：" + res);//5
	}

	public static void main(String[] args) {
		int[] a = { 1, 2, 3, 2, 4, 3, 5, 4, 1 };
		method(a);
	}

但是这种方法只适用于，其他数出现的次数为偶数次的情况，如果其他每个数都出现n次（n可以是奇数也可以是偶数），该如果找出只出现一次的那个数呢？

方法如下：


我们建立一个长度为32的数组bit，bit[i]储存的是a数组中，所有数第i位上为1的总个数。（位数是从右往左数的，最右边是第0位）

我们将bit数组中的每一个数除以3，如果除不尽，说明我们最终要找的那个数在这个位上为1

	public static int method(int[] a) {
		int[] bit = new int[32];
		int len = a.length;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < bit.length; j++) {
				bit[j] += ((a[i] >> j) & 1);
			}
		}
		int res = 0;
		for (int i = 0; i < bit.length; i++) {
			if (bit[i] % 3 != 0) {
				res += (1 << i);
			}
		}

		return res;
	}

	public static void main(String[] args) {
		int[] a = { 1, 2, 1, 2, 4, 2, 4, 4, 1, 3 };
		System.out.println(method(a));// 3
	}