这是一个创建于 4003 天前的主题，其中的信息可能已经有所发展或是发生改变。
说在一个整型数组里，所有的数都重复了两次，仅有两个数是不重复的，如何在时间 O(n) 和空间 O(1) 内找出这两个数？
想了好久，关键是空间复杂度不符合。有种被虐的痛苦
想了好久，关键是空间复杂度不符合。有种被虐的痛苦
 |
1
cxe2v 2013-12-27 11:39:07 +08:00
数组是有序还是无序的？
|
 |
2
34D 2013-12-27 11:40:15 +08:00  2
异或。
|
 |
4
dingyaguang117 2013-12-27 12:04:59 +08:00
2个数不重复啊。。
|
 |
5
vainly 2013-12-27 12:41:10 +08:00
//用来存放找出来的数据
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()); |
 |
6
327beckham 2013-12-27 12:46:24 +08:00 1
如果不是编程之美上有这个题目，就是剑指offer上有这个题目。
先从只有一个数不重复的题目扩展开来即可。 |
|
7
327beckham 2013-12-27 12:52:18 +08:00 2
还是直接说答案吧，如果是只有一个数不重复的话，所有数字抑或，即可找到那个数。
现在扩展成两个数了，那么第一步还是全部异或，最后剩下的那个数A，就是两个单独数字的异或了。这个时候，在A中随便找一个某个bit为1的位置。按照这个bit是否为1，可以将题目中的原有的数组分成两个数组了，而且这两个数组中分别有一个只出现一次的数。 |
 |
8
pagict OP |
|
9
327beckham 2013-12-27 12:54:46 +08:00
时间复杂度：整个数组扫描两遍，空间复杂度：记录几个变量即可。
|
|
10
327beckham 2013-12-27 12:59:22 +08:00 1
@pagict 跟你说个最最简单的例子吧：1 64 3 3 4 4 5 5 6 6 7 7这个数组全部异或之后，肯定得到的是1和64的异或的结果，得到的数字是3.二进制也就是0100 0001. 从右往左数的第1个bit是个1吧。那就按照第一个bit是否为1，可以将原有数组的所有数字分成两组了。
|
|
11
327beckham 2013-12-27 13:00:06 +08:00
@pagict 上面一句写错了，1异或64是65.。。我写成3了
|
|
12
pagict OP @327beckham 异或是每个数组元素和谁异或
|
 |
13
anewg 2013-12-27 13:07:20 +08:00
@327beckham 没看懂你的解法，楼主的题目是要时间 O(n) 和空间 O(1)，你这个再分数组不就超过了吗？而且分成两组然后呢?
|
|
17
327beckham 2013-12-27 13:39:32 +08:00 1
@anewg 我说的分组也就是 逻辑理解上分组而已嘛，并没有说另外开个空间存这两个数组啊。第二次扫描原有数组的时候，某一类异或结果存到X，另外一类异或存到Y。最后答案就是X和Y这两个数了嘛。
|
|
18
327beckham 2013-12-27 13:41:36 +08:00
@pagict 1异或2异或3和 2异或3异或1，结果一样，交换律。不在乎原有顺序
|
 |
19
biaobiaoqi 2013-12-27 14:45:12 +08:00
@327beckham 很赞的思路！
|
 |
20
Sdhjt 2013-12-27 14:50:33 +08:00
@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) } |
 |
21
duzhe0 2013-12-27 15:41:01 +08:00
我估计是题目错了， 有两个数不重复在O(n)时间和O(1)空间应该是不可能找出来的。或者说， 我们没有办法在O(n)的时间里利用O(1)的空间提取出这么大的信息量。
|
|
29
Sdhjt 2013-12-27 16:15:39 +08:00 1
|
 |
30
stackpop 2013-12-27 16:17:22 +08:00 1
@duzhe0 显然可以
1^1^3^5 = 3^5 = 6 = （0110）二进制 按倒数第二位为1来分组，可以分成 第一组 1 1 5 ,1^1^5 = 5 第二组 3 故结果为5 和 3 这里的要点是，第一次抑或的结果，某一位为1，说明要找的这两个数该位值肯定不同（想想抑或的含义），而之前那些相同的两个数肯定在同一组。 ========== 扩展一下到3个数只出现一次，其它都出现两次，大家再考虑下，呵呵。 2个数的比较容易想到 |
|
31
duzhe0 2013-12-27 16:22:10 +08:00
明白了
|
 |
32
Virtao 2013-12-27 16:23:35 +08:00 1
|
 |
33
nagato 2013-12-27 18:05:40 +08:00
2楼答案简单明了
|
|
34
pagict OP @327beckham 终于懂了……好腻害的说！谢啦
|
|
35
327beckham 2013-12-28 01:16:33 +08:00
@pagict 如果你和我一样是应届生或者最近在找编程类IT方面的工作的话，强烈建议你通读和精读两本书《编程之美》《剑指offer》，和July的博客。。。这些知识在方方面面会给你很大的帮助，不仅仅是面试
|
 |
36
scola 2013-12-28 08:45:06 +08:00
@327beckham 赞，受教了
|
|
37
dingyaguang117 2014-01-03 19:40:01 +08:00
@327beckham 果然牛逼~
|
Select Language