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

83 阅读 0 评论 55 点赞

我是靠谱客的博主感动飞机，这篇文章主要介绍一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。，现在分享给大家，希望可以做个参考。

基础

与运算：& ：两者都为1结果才为1，否则为0 ， eg：1&1=1, 1&0=0, 0&1=0, 0&0=0

或运算：|：两者都为0结果才为0，否则为1， eg：1|1 = 1, 1|0 = 1, 0|1 = 1, 0|0 = 0
非运算：~：1取0，0取1， eg：~1 = 0, ~0 = 1 eg：~(1001) = 01110
异或运算:^：两者相等才为0,不等则为1 eg: 1^1=0, 1^0=1, 0^1=1, 0^0=0

代码如下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Num {
//第一步求出异或结果
//第二步找到异或结果不为 0 的作为标签 flag （与的运算都为 1 才为 1）
//第三步用 flag 标签将数组分为两个子数组，异或掉相同的数字，最后得到 num1 和 num2
public void findNums(int[] arr, int num1[], int num2[]) {
if (arr.length < 2) return;
int result = 0;
int flag = 1;
//循环左后 result 等于两个不同的数异或结果
for (int i = 0; i < arr.length; i ++) result ^= arr[i];
//找到异或结果最低位不为 1 的数，作为标签
while ((result & flag) == 0) flag <<= 1;
//利用 flag 标签将 arr 分为两个子数组
//一个子数组的二进制该位是 1，另一个子数组的二进制的该位是 0
for (int i = 0; i < arr.length; i++) {
if ((flag & arr[i]) == 0) num2[0] ^= arr[i];//该位是 0
else num1[0] ^= arr[i];
}
System.out.println(num1[0]);
System.out.pritnln(num2[0]);
}
public static void main (String[] args) {
Num num = new Num();
int[] arr = {1,2,2,3,4,4};
int[] num1 = {0};
int[] num2 = {0};
num.fundNums(arr, num1, num2);
}
}