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

刷题--数组中只出现一次的数字

程序员文章站 2022-07-15 12:21:43
...

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

第一想法是用哈希表,但其实浪费了空间。
我们可以利用异或运算的特性,任何一个数字异或自己都等于0。先考虑如果一个数组中只有一个数字只出现一次,那么只要从头到尾依次异或数组中的每一个数字就能得到那个只出现了一次的数字。在这个问题里,我们可以把原始数组分成两个子数组,使得每个子数组包含一个只出现一次的数字。由于这两个数肯定不一样,所以数组中所有数字的异或结果至少有一位为1,记录下第一个为1的位置,按照这个位置是否为1将数组分成两部分。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        num = array[0]
        for item in array[1:]:
            num = num ^ item

        index = 0
        while not num & 1:
            num = num >> 1
            index += 1

        a, b = 0, 0
        for item in array:
            temp = item

            for _ in range(index):
                temp = temp >> 1

            if temp & 1:
                a = a ^ item
            else:
                b = b ^ item

        return [a, b]