题目要求

出处:https://www.v2ex.com/t/94742

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

思路分析

假设这组数字为:

23, 23, 19, 19, 1, 88, 88, 3, 3, 2, 56, 56

两个不重复的数字设为a1和a2。

将所有数字异或:

x = 23^23^19^19^1^88^88^3^3^2^56^56 = 1^2

经过这一步,我们找到了两个不重复数字a1和a2的异或后的结果x。我们还需要将这两个数字分开。下面就是一个比较重要的思路了,x是两个数异或的结果,也就是说,x保存了两个数字各比特位的差异。相同的位为0,不相同的位为1。我们找出不相同的位,便可以将整组数字分为两组。

例如:这里x = 3 = 00000011B,从这里看出,a1和a2在1~2比特位上是不一样的。我们随便选取其中一位,比如右起第一位为区分位,这样所有数字可以分为两组:

比特位末位为0:88, 88, 2, 56, 56
比特位末位为1:23, 23, 19, 19, 1, 3, 3

这样分完后,我们发现,a1和a2分到不同的组里了。将其中任意一组所有数字进行异或,便可以得出其中一个不重复的数字:

a1 = 88^88^2^56^56 = 2
a2 = a1^x = a1^a1^a2 = 1

这样,我们只需要遍历两遍数组,就可以找出这两个数。

代码实例(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)
}

异或的运算律

以上题目充分考察了异或的运算律以及异或后的结果所代表的含义。下面内容转自:http://longzxr.blog.sohu.com/190676432.html,内容稍作修改。

异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示。其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。

简单理解就是相同为0,不同为1。

  • 异或运算律

    1. 交换律:a^b == b^a
    2. 结合律:(a^b)^c == a^(b^c)
    3. 对于任何数x,都有x^x=0,x^0=x
    4. 自反性:a^b^b = a^0 = a

异或运算最常见于多项式除法,不过它最重要的性质还是自反性:a^b^b = a^0 = a,即对给定的数a,用同样的运算因子b作两次异或运算后仍得到a本身。这是一个神奇的性质,利用这个性质,可以获得许多有趣的应用。 例如,所有的程序教科书都会向初学者指出,要交换两个变量的值,必须要引入一个中间变量。但如果使用异或,就可以节约一个变量的存储空间: 设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值 表达式 (值) :

A = A ^ B (a ^ b)
B = B ^ A (b ^ a ^ b = a)
A = A ^ B (a ^ b ^ a = b)

类似地,该运算还可以应用在加密,数据传输,校验等等许多领域。

类似的题目

google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数?

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?