数组中只出现一次的数字--python

#一个整型数组中除了两个数字之外，其他数字都出现了两次。找到这个两个只出现一次是数字。要求时间复杂度O(n),空间复杂度O(1)
#思路1：字典，以数组中的数字为键，出现次数为值，最后找到值为1对应的键
def findOnceNum(arr):
    if len(arr) < 2:
        return None
    dict, res = {}, []
    for i in arr:
        dict[i] = dict.get(i, 0) + 1
    for key in dict:
        if dict[key] == 1:
            res.append(key)
    return res

#思路2：异或思想,任何一个数字异或它自己都是0
#用异或求解。异或运算的性质：任何一个数字异或它自己都等于0 。如果数组中只有一个数字出现过一次，其余数字都出现了两次；这样的话如果我们从头到尾依次异或数组中的每一个数字，
# 那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，
# 而其它数字都出现两次。在两个子数组中分别求出这两个只出现一次的数字。 还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。
# 因为其它数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0 ，也就是说在这个结果数字的二进制表示中至少就有一位为1 。
# 我们在结果数字中找到第一个为1的位的位置，记为第N 位。现在我们以第N 位是不是1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N 位都为1 ，
# 而第二个子数组的每个数字的第N 位都为0 。现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其它数字都出现了两次。因此到此为止，所有的问题我们都已经解决。
def findOnceNum(arr):
    if len(arr) < 2:
        return None
    tmp, index = 0, 1  # 得到最终的结果，两个只出现一次的数字异或的结果
    for i in arr:
        tmp = tmp ^ i
    # 在结果数字中找到第一个为1的位
    while tmp & index == 0:
        index = index << 1
    res1, res2 = 0, 0
    for num in arr:
        # 将原始数组分为两个子数组
        if num & index == 0:
            res1 = res1 ^ num
        else:
            res2 = res2 ^ num
    return [res1, res2]

# print(findOnceNum([2,4,3,6,3,2,5,5]))

最后

以上就是年轻大侠为你收集整理的数组中只出现一次的数字--python的全部内容，希望文章能够帮你解决数组中只出现一次的数字--python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。