首页 > 代码库 > 数组中只出现一次的数字

数组中只出现一次的数字

题目

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

 

分析

  假设这两个数字为A和B,将数组中的所有数字进行异或,最后结果为all=A^B;然后找到all二进制形式最后一个1所在的位置,如all=110,则设置n=010;然后遍历数组,将array[i]&n!=0的进行异或,可得到A或B其中的一个,在将array[i]&n==0的进行异或,可得到另一个,分别放入num1和num2中。

 

代码

 1     public static void FindNumsAppearOnce(int [] array, int[] num1, int[] num2) {
 2         int all = 0;
 3         for(int i=0;i<array.length;i++){
 4             all ^= array[i];
 5         }
 6         int count = 0;
 7         while((all & 1) !=1){
 8             all = all>>1;
 9             count++;
10         }
11         int n = 1<<count;
12         for(int i=0;i<array.length;i++){
13             int temp = array[i];
14             if((temp & n)!=0){
15                 num1[0] ^= temp;
16             }
17             else{
18                 num2[0] ^= temp;
19             }
20         }
21 
22     }

 

数组中只出现一次的数字