欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer(40)数组中只出现一次的两个数字

程序员文章站 2022-03-08 16:23:22
...
/**
 * 题目:数组中数字出现的次数。数组中只出现一次的两个数字,要求空间o(1)时间o(n). eg:{2,4,3,6,3,2,5,5}结果是4、6
 * 思路:剑指offer 异或思想,任何数和它本身异或的值为0.
 * 我们依旧从头到尾异或每个数字,那么最终的结果就是这两个只出现一次的数字的异或结果,由于两个数不同,因此这个结果数字中一定有一位为1,把结果中第一个1的位置记为第n位。
 * 因为是两个只出现一次的数字的异或结果,所以这两个数字在第n位上的数字一定是1和0。
 * eg:对每个数字进行异或得到结果0010,根据倒数第二位是不是1将数组分成2组{2,3,6,3,2}和{4,5,5} 再分别对两个子数组求异或
 * 
 * @author hexiaoli
 */
public class Main {
	public static int[] FindNumsAppearOnce(int[] array) {
		// 边界
		if (array.length < 2 || array == null) {
			return null;
		}
		int resultExclusiveOR = 0;
		int length = array.length;
		for (int i = 0; i < length; i++) {
			resultExclusiveOR ^= array[i];
		}
		// 首次出现1的情况
		int indexOf1 = 0;
		while (((resultExclusiveOR & 1) == 0) && (indexOf1 <= 4 * 8)) {
			resultExclusiveOR = resultExclusiveOR >> 1;
			indexOf1++;
		}
		int result[] = new int[] { 0, 0 };
		// 分为两组
		for (int i = 0; i < length; i++) {
			if (((array[i] >> indexOf1) & 1) == 1)
				result[0] ^= array[i];
			else
				result[1] ^= array[i];
		}
		return result;
	}

	public static void main(String[] args) {
		int[] array = new int[] { 2, 4, 3, 6, 3, 2, 5, 5 };
		int[] result = FindNumsAppearOnce(array);
		System.out.println(result[0] + " and " + result[1]);
	}
}