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

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

[duzhe0]

我估计是题目错了， 有两个数不重复在O(n)时间和O(1)空间应该是不可能找出来的。或者说， 我们没有办法在O(n)的时间里利用O(1)的空间提取出这么大的信息量。

[duzhe0]

@Sdhjt
这个肯定不行的， 你自己随便构造一个例子试试。

[duzhe0]

@vainly 你这个至少是O(n)的空间复杂度。

[Sdhjt]

@duzhe0 例子是刚写的，已经经过我测试了，或者你可以举个例子，我放程序里测一下。

[duzhe0]

@Sdhjt 1， 1， 3， 5

[duzhe0]

@Sdhjt
或者2,2,3,5

[Sdhjt]

@duzhe0
Result : 3 5

[duzhe0]

@Sdhjt
?
难道我错了？
你试试
1, 1, 2, 2, 4, 4, 3, 5

[Sdhjt]

@duzhe0
Result : 3 5
@327beckham 的思路是对的。

[stackpop]

@duzhe0 显然可以
1^1^3^5 = 3^5 = 6 = （0110）二进制

按倒数第二位为1来分组，可以分成
第一组 1 1 5 ,1^1^5 = 5
第二组 3
故结果为5 和 3

这里的要点是，第一次抑或的结果，某一位为1，说明要找的这两个数该位值肯定不同（想想抑或的含义），而之前那些相同的两个数肯定在同一组。
==========

扩展一下到3个数只出现一次，其它都出现两次，大家再考虑下，呵呵。
2个数的比较容易想到

[duzhe0]

明白了

[Virtao]

好妙的思路，我写了篇博文，总结了一下：

http://blog.virtao.org/articles/163.html

@327beckham
@duzhe0

[nagato]

2楼答案简单明了

[pagict]

@327beckham 终于懂了……好腻害的说！谢啦

[327beckham]

@pagict 如果你和我一样是应届生或者最近在找编程类IT方面的工作的话，强烈建议你通读和精读两本书《编程之美》《剑指offer》，和July的博客。。。这些知识在方方面面会给你很大的帮助，不仅仅是面试

[scola]

@327beckham 赞，受教了

[dingyaguang117]

@327beckham 果然牛逼~