我也遇到一个面试题 冥思苦想不出 夜不能寐 求解

[pagict]

说在一个整型数组里，所有的数都重复了两次，仅有两个数是不重复的，如何在时间 O(n) 和空间 O(1) 内找出这两个数？

想了好久，关键是空间复杂度不符合。有种被虐的痛苦

[cxe2v]

数组是有序还是无序的？

[34D]

异或。

[pagict]

@cxe2v 没提，想来是无序的。要是有序那就好做了

@34D 分别跟谁异或啊

[dingyaguang117]

2个数不重复啊。。

[vainly]

//用来存放找出来的数据
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
//整数数组
Integer[] array = {1,1,2,2,3,3,4,5,5,6,6,7};
for(int i=0;i<array.length;i++){
Integer key = array[i];
if(map.get(key)==null){
map.put(key, 1);
}else{
map.remove(key);
}
}
//输出结果
System.out.println(map.toString());

[327beckham]

如果不是编程之美上有这个题目，就是剑指offer上有这个题目。
先从只有一个数不重复的题目扩展开来即可。

[327beckham]

还是直接说答案吧，如果是只有一个数不重复的话，所有数字抑或，即可找到那个数。
现在扩展成两个数了，那么第一步还是全部异或，最后剩下的那个数A，就是两个单独数字的异或了。这个时候，在A中随便找一个某个bit为1的位置。按照这个bit是否为1，可以将题目中的原有的数组分成两个数组了，而且这两个数组中分别有一个只出现一次的数。

[pagict]

@dingyaguang117 形如 [1,2,3,4,5,4,7,1,2,3]

@vainly 空间复杂度不对啊

@327beckham 是有两个数不重复

[327beckham]

时间复杂度：整个数组扫描两遍，空间复杂度：记录几个变量即可。

[327beckham]

@pagict 跟你说个最最简单的例子吧：1 64 3 3 4 4 5 5 6 6 7 7这个数组全部异或之后，肯定得到的是1和64的异或的结果，得到的数字是3.二进制也就是0100 0001. 从右往左数的第1个bit是个1吧。那就按照第一个bit是否为1，可以将原有数组的所有数字分成两组了。

[327beckham]

@pagict 上面一句写错了，1异或64是65.。。我写成3了

[pagict]

@327beckham 异或是每个数组元素和谁异或

[anewg]

@327beckham 没看懂你的解法，楼主的题目是要时间 O(n) 和空间 O(1)，你这个再分数组不就超过了吗？而且分成两组然后呢?

[anewg]

@pagict 两两异或过去，相同的元素异或都会为0，最后0跟那个没重复的单个元素异或得那元素本身

[pagict]

@anewg 题目没说已经归类好了啊 若是形如 [1,2,3,4,5,4,7,1,2,3] 呢

[anewg]

@pagict 那个异或的只针对1个不重复

[327beckham]

@anewg 我说的分组也就是 逻辑理解上分组而已嘛，并没有说另外开个空间存这两个数组啊。第二次扫描原有数组的时候，某一类异或结果存到X，另外一类异或存到Y。最后答案就是X和Y这两个数了嘛。

[327beckham]

@pagict 1异或2异或3和 2异或3异或1，结果一样，交换律。不在乎原有顺序

[biaobiaoqi]

@327beckham 很赞的思路！

[Sdhjt]

@327beckham 思路很赞，只需要扫描两遍数组就可以。下面用Go实现了一个例子：

package main

import (
"fmt"
)

func main() {
nums := []int{23, 23, 19, 19, 1, 88, 88, 3, 3, 2, 56, 56}

//设两个不重复的数为a1和a2，x = a1 ^ a2，bits为a1和a2某个不一致的位
var a1, a2, x, bits int

//将所有的数字异或，得到的结果就为x，因为重复的数经过异或后都为0
for _, v := range nums {
x = x ^ v
}

//找出a1和a2某个不一致的位，换句话说，就是找出x为1的位（当然，x为1的位有很多，我们这找的是x从右往左第一个为1的位）
bits = 1
for i := 31; i >= 0; i++ {
if x&bits != 0 {
break
}
bits = bits << 1
}

//舍去所有bits位为0的位，将剩下的数字全部异或，这样就能得出两个不重复的数字其中的一个
for _, v := range nums {
if v&bits != 0 {
a1 = a1 ^ v
}
}

//根据x和a1可以很容易求出a2
a2 = x ^ a1

fmt.Println("Result : ", a1, a2)
}