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

63 阅读 0 评论 42 点赞

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

概述

基础

与运算：& ：两者都为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

代码如下

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);
}
}