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

95 阅读 0 评论 63 点赞

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

概述

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

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。例如数组为{1，3，5，7，1，3，5，9}，找出7和9。

二、解答：

1、运用异或运算符的解法

我们先考虑上述问题的简单版本：一个数组里面只有一个数字出现一次，其他都出现两次，请找出这个数字。


这个问题可以可以使用用异或的性质解决。异或的性质：对于整数a,有
（1） a^a=0
（2）a^0=a
（2）a^b^c=a^(b^c)=(a^c)^b
利用以上的性质，上面的题目的解法为：

public static void findNumAppearOnce(int[] arr) {
int result = 0;
for (int i = 0; i < arr.length; i++) {
result ^= arr[i];
}
System.out.println(result);
有了以上的基础，解文章开始时提出的问题的思路如下：

(1)对于出现两次的元素，使用“异或”操作后结果肯定为0，那么我们就可以遍历一遍数组，对所有元素使用异或操作，那么得到的结果就是两个出现一次的元素的异或结果。

(2)因为这两个元素不相等，所以异或的结果肯定不是0，也就是可以再异或的结果中找到1位不为0的位，例如异或结果的最后一位不为0。

(3)这样我们就可以最后一位将原数组元素分为两组，一组该位全为1，另一组该位全为0。

(4)再次遍历原数组，最后一位为0的一起异或，最后一位为1的一起异或，两组异或的结果分别对应着两个结果。

复制代码
/*
解法1：
1、思路：
(1)对于出现两次的元素，使用“异或”操作后结果肯定为0，那么我们就可以遍历一遍数组，对所有元素使用异或操作，那么得到的结果就是两个出现一次的元素的异或结果。
(2)因为这两个元素不相等，所以异或的结果肯定不是0，也就是可以再异或的结果中找到1位不为0的位，例如异或结果的最后一位不为0。
(3)这样我们就可以最后一位将原数组元素分为两组，一组该位全为1，另一组该位全为0。
(4)再次遍历原数组，最后一位为0的一起异或，最后一位为1的一起异或，两组异或的结果分别对应着两个结果。
2、复杂度：
（1）时间复杂度：第一次循环，将所有元素异或得到对应结果，时间开销为O(n)；第二次循环，找出第一次异或结果为1的位，时间开销为O(32)；第三次循环，根据为1的位将元素分为两组进行异或得到两个结果，时间复杂度为O(n)，所以总的时间复杂度为T(n) = 2*O(n)+O(32) = O(n)。
（2）空间复杂度：常数，因为只分配了两个空间用于结果的保存，因此空间复杂度为常数。
*/

public static int[] findNumsAppearOnce2(int[] arr) {
if(arr.length < 2)
return arr;
int[] result = new int[2];
//要返回的结果
int res = arr[0];
//第一次对所有元素进行亦或操作结果
for(int i=1; i<arr.length; i++) {
res ^= arr[i];
}
int bitIndex = 0;
for(int i=0; i<32; i++) {
//找出亦或结果为1的位。
if((res>>i & 1) == 1) {
bitIndex = i;
break;
}
}
for(int i=0; i<arr.length; i++) { //根据bitIndex为1，将元素分为两组
if((arr[i] >> bitIndex & 1) == 1)
result[0] ^= arr[i];
//对应位为1，亦或得到的结果
else
result[1] ^= arr[i];
//对应位为0，亦或得到的结果
}
return result;
}

复制代码
2、运用HashMap的解法

(1）思路：

使用一个Map，Map对应的键值key就是数组中的元素，value就是这个元素出现的次数。这样我通过一次遍历数组中的元素，
如果元素出现在map中，则将其对应的value加1，否则将元素添加到map中，这样遍历一遍数组，我们就可以得到数组中每个元素对应出现的次数，
然后再通过遍历一遍map，返回value为1对应的key就是我们需要求得元素。

复制代码
/*
解法2：
（1）思路：这个可以可以使用一个Map，Map对应的键值key就是数组中的元素，value就是这个元素出现的次数。这样我
通过一次遍历数组中的元素，如果元素出现在map中，则将其对应的value加1，否则将元素添加到map中，这样遍历一遍数组，我们就可以得到数组中每个元素对应出现的次数，然后再通过遍历一遍map，返回value为1对应的key就是我们需要求得元素。
（2）时间复杂度：因为首先需要遍历一遍数组，时间开销为O(n)，构建完map后需要遍历一遍map找到value为1的元素，而map的个数为n/2，时间开销为O(n/2)，所以总的时间开销为O(n)。
（3）空间复杂度：因为需要建立一个map，而且最后map的大小为n/2，所以空间复杂度为O(n)。
*/
public static void findNumsAppearOnce1(int[] arr) {
//Map对应的键值key就是数组中的元素，value就是这个元素出现的次数
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i : arr) {
if (hashMap.containsKey(i)) {
hashMap.put(i, hashMap.get(i) + 1); //如果存在，value值加1
} else {
hashMap.put(i, 1); //如果不存在，存入hashMap,value值等于1
}
}


//遍历一遍map，返回value为1对应的key就是我们需要求得元素
Set<Integer> set = hashMap.keySet();
for (int i : set) {
if (hashMap.get(i) == 1) {
System.out.print(i+" ");
}
}
}