欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer_编程题40:数组中只出现一次的数字(异或)

程序员文章站 2022-07-15 12:08:47
...

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

要求时间复杂度是O(n),空间复杂度是O(1)。

牛客网:链接

空间复杂度是O(1),所以不能用字典或者列表。如果前几行代码有一个O(n)的循环,后几行代码还有一个O(n)的循环,那么时间复杂度是O(n)+O(n),其实就是O(n)。

我们知道异或的一个性质是:任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字。比如数组{4,5,5},我们先用数组中的第一个元素4(二进制形式:0100)和数组中的第二个元素5(二进制形式:0101)进行异或操作,0100和0101异或得到0001,用这个得到的元素与数组中的三个元素5(二进制形式:0101)进行异或操作,0001和0101异或得到0100,正好是结果数字4。这是因为数组中相同的元素异或是为0的,因此就只剩下那个不成对的孤苦伶仃元素。

现在好了,我们已经知道了如何找到一个数组中找到一个只出现一次的数字,那么我们如何在一个数组中找到两个只出现一次的数字呢?如果,我们可以将原始数组分成两个子数组,使得每个子数组包含一个只出现一次的数字,而其他数字都成对出现。这样,我们就可以用上述方法找到那个孤苦伶仃的元素。

我们还是从头到尾一次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次,在异或中全部抵消了。由于两个数字肯定不一样,那么异或的结果肯定不为0,也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置,记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组,第一个子数组中每个数字的第n位都是1,而第二个子数组中每个数字的第n位都是0。

A和0异或的结果还是A

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        if len(array) < 2:
            return None
        remain, index = 0, 1
        for num in array:
            remain = remain ^ num
        while (remain & index) == 0:
            index = index << 1
        res1,res2 = 0,0
        for num in array:
            '''
            一定要判断是否等于0,不能判断是否等于1。
            '''
            if (num & index) == 0:
                res1 = res1^num
            else:
                res2 = res2^num
        return [res1,res2]