数组之数组中只出现一次的数字

1.本题知识点

   位运算&＃xff0c;异或

2. 题目描述

  一个整型数组里除了两个数字之外&＃xff0c;其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

3. 思路

   这题考察的是异或操作&＃xff0c;即对应位上值相同为0&＃xff0c;值不同为1。

  ① 异或操作满足交换结合律&＃xff0c;比如A ^ B ^ A &＃61; B ^ (A ^A) &＃61; B ^ 0 &＃61; B。所以&＃xff0c;数组中数字两两异或&＃xff0c;若其中有2个单次出现的数字&＃xff0c;最后得到的结果就是这2个单次数字的异或结果&＃xff0c;其他出现2次的数字都异或抵消掉了。

  ② 通过①的分析&＃xff0c;假设数组中只有一个单次的数字&＃xff0c;那么异或后的结果就是这个数&＃xff0c;所以&＃xff0c;考虑把原数组分开&＃xff0c;通过什么分开呢&＃xff1f;原数组异或结果位数为1的索引值&＃xff0c;区分开2个单次的数&＃xff0c;最后分别求2个子数组异或的结果即可。

   举例说明&＃xff1a;

   ③ 如何知道是哪个位上不同呢&＃xff1f;比如上面是第n &＃61;3位不同&＃xff0c;现在我们要找到这个n。

   方法&＃xff1a;通过【原数组异或结果】【从后往前找到第一个1】的位置即可。

   举例&＃xff1a;

   Java版本&＃xff1a;

package com.algorithm.array;/*** 一个整型数组里除了两个数字之外&＃xff0c;其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。* 时间复杂度O(n)&＃xff0c;空间复杂度O(1)* &＃64;author wxq**/
public class NumXOR {public static void main(String[] args) {int [] array &＃61; {2,4,3,6,3,2,5,5};int[] num1 &＃61; new int[array.length];int[] num2 &＃61; new int[array.length];findNumsAppearOnce(array, num1, num2);System.out.println(num1[0] &＃43; " " &＃43; num2[0]);}/*** * &＃64;param array* &＃64;param num1 存放返回结果* &＃64;param num2*/static void findNumsAppearOnce(int [] array,int num1[] , int num2[]){if(array &＃61;&＃61; null || array.length &＃61;&＃61; 0){num1[0] &＃61; -1;num2[0] &＃61; -1;}//1. 求原数组两两异或结果int bitResult &＃61; 0;for(int i &＃61;0 ; i < array.length; i&＃43;&＃43;){bitResult ^&＃61; array[i];}//2. 找到倒数第一个1的位置int index &＃61; findFirst1(bitResult);//3. 根据index位上是不是1切分原数组&＃xff0c;并将子数组两两异或。for(int i &＃61;0 ; i < array.length; i&＃43;&＃43;){if(isBit1(array[i],index)){num1[0] ^&＃61; array[i];}else{num2[0] ^&＃61; array[i];}}//4. 最终得到单次出现数字num1[0] num2[0]}/*** 找到原数组异或结果的倒数第一个1的位置* &＃64;param bitResult* &＃64;return*/static int findFirst1(int bitResult){int index &＃61; 0;while((bitResult & 1) &＃61;&＃61; 0){bitResult >>&＃61; 1;index&＃43;&＃43;;}return index;}/*** 判断数字第index位置上是不是1* &＃64;param target* &＃64;param index* &＃64;return*/static boolean isBit1(int target, int index){return ((target >> index) & 1) &＃61;&＃61; 1;}
}