hanyeah

数组中唯一出现1次的数|唯一出现2次的数

题目

一个整型数组里除了1个数字之外，其他的数字都出现了两次，请写程序找出这个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)，例如输入数组｛2, 4, 3, 3, 2, 5 }，因为只有 4 这个数字只出现一次，其他数字都出现了两次，所以输出 4

分析  

本题以及延伸题目，在剑指offer上有详细描述。利用异或的特性，x^y^x=y^x^x=y。对数组所有元素一次进行异或操作，最终得到的值就是那个只出现一次的数字。

代码

var a = [2,4,3,2,3,5,5];
console.log(findOnceNum(a));

/**
 * 数组中唯一出现1次的数。
 */
function findOnceNum(a){
	var ret = 0;
	var len = a.length;
	for(var i = 0; i < len; i++){
		ret = ret^a[i];
	}
	return ret;
}

那么，当数组中有2个只出现1次的数字呢？

例如输入数组｛2, 4, 3, 3, 6, 2, 5 }，因为4和6 这两个数字都只出现一次，其他数字都出现了两次，应输出 4，6

思路分析 

假设两个只出现一次的数字分别为a、b，对数组元素进行两两异或后得到的值为c,可知c=a^b。因为a和b一定不同，所以c不等于0，那么c的二进制表示中一定有一位是1，即a,b在此位上分别为0,1或1,0。假设该位置是从低位起第x位，那么将数组分成两组，一组中的数字在第x位是0，另一组中的数字在第x位是1，则a和b分别属于两个子数组。分别求子数组中唯一只出现1次的数字，即可得到a和b。

代码

var a = [2,4,3,2,3,5,5,7];
console.log(findOnceNums(a));

function isTrueBit(num, index){
	return (num>>index) & 0x01;
}

/**
 * 数组中两个出现1次的数。
 */
function findOnceNums(arr){
	var xor = 0;
	var len = arr.length;
	for(var i = 0; i < len; i++){
		xor = xor^arr[i];
	}
	//
	var index = 0;
	while(index < 32){
		if(isTrueBit(xor, index)){
			break;
		}
		index++;
	}
	//
	var a = 0;
	var b = 0;
	for(var i = 0; i < len; i++){
		if(isTrueBit(arr[i])){
			a = a^arr[i];
		} else {
			b = b^arr[i];
		}
	}
	return [a, b];
}

延伸1：

如果要求数组中唯一只出现1次的3个数字呢？

思路是一样的，3个数字的二进制表示中必有1位，一个数字a在此位上是1，其他两个数字b、c在此位上是0。先以此将数组分为两组,求出a,再求子数组中唯一出现1次的两个数字b和c。

延伸2：

找出数组中唯一出现两次的数。

假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次 分析 从题目中可以知道，这1001个整数是1到1000的连续整数（任意排列）加上一个多出1次的任意数字（在1到1000之间）。那么xor_num=1^2^3^···X···N-1^N,xor_num2=1^2^3^···X^X···N-1^N,将xor_num和xor_num2异或即可得到X 。

延伸3：

找出数组中唯一出现两次的数（任意整数数组）

一个数组，除了有1个数字出现2次外，其余数字均出现1次，求出现2次的那个数字 本题只好用hash的内存方式记录次数了，暂时没想到好的方法