0415:时间复杂度和空间复杂度详解+剑指offer:29、数组中只出现一次的数字

77 阅读 0 评论 51 点赞

我是靠谱客的博主调皮冬天，最近开发中收集的这篇文章主要介绍0415:时间复杂度和空间复杂度详解+剑指offer:29、数组中只出现一次的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

介绍时间复杂度和空间复杂度的博客，忘记可以复习一下～
算法的时间和空间复杂度：https://blog.csdn.net/jsjwk/article/details/84315770
算法的时间和空间复杂度的计算： https://blog.csdn.net/daijin888888/article/details/66970902
时间复杂度和空间复杂度的简单讲解：https://blog.csdn.net/HaloTrriger/article/details/78994122

29、数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
笔记：用python实现很简单，和前面找超过长度一半的数字很像，解题时，刚开始没注意输出，要是列表，感觉剑指offer应该给输入输出列子，好多没有，不过本地调试时发现，py3把数组当做集合，直接删除重复元素，2则不会～
解法1：

from collections import Counter
class Solution:
    def FindNumsAppearOnce(self, array):
        num = Counter(array)
        res = []
        for k,v in num.items():
            if v == 1:
                res.append(k)
        return res

看到评论区的：

链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
来源：牛客网

from collections import Counter
class Solution:
 
    def FindNumsAppearOnce(self, array):
 
        return list(map(lambda c:c[0],Counter(array).most_common()[-2:]))

解法2：
HashMap法

链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
来源：牛客网

hashMap法
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        hashMap = {}
        for i in array:
            if str(i) in hashMap:
                hashMap[str(i)] += 1
            else:
                hashMap[str(i)] = 1
        res = []
        for k in hashMap.keys():
            if hashMap[k] == 1:
                res.append(int(k))
        return res

如果要求要求时间复杂度是O(n)，空间复杂度是O(1)。则上面的解法均不满足，只能考虑其他的解法，看评论区提到的都是异或解法，在评论区一直看不太懂，主要自己知识不足。
查了Python文档，异或是以两个数字的二进制按位异或，不是数字直接比相不相同
找了博客，终于看到最详细的解答了～～～

例：{2,4,3,6,3,2,5,5}

这个数组中只出现一次的两个数分别是4和6。怎么找到这个两个数字呢？

我们先不看找到俩个的情况，先看这样一个问题，如何在一个数组中找到一个只出现一次的数字呢？比如数组：{4,5,5}，唯一一个只出现一次的数字是4。

我们知道异或的一个性质是：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字。比如数组{4,5,5}，我们先用数组中的第一个元素4（二进制形式：0100）和数组中的第二个元素5（二进制形式：0101）进行异或操作，0100和0101异或得到0001，用这个得到的元素与数组中的三个元素5（二进制形式：0101）进行异或操作，0001和0101异或得到0100，正好是结果数字4
现在好了，我们已经知道了如何找到一个数组中找到一个只出现一次的数字，那么我们如何在一个数组中找到两个只出现一次的数字呢？如果，我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。

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

举例：{2,4,3,6,3,2,5,5}

我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。
笔记：算法解答真的有些复杂，适合大神呀主要先看懂了思路，以后提升了，再把解答自己写一下～
**

解答3：

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if len(array) <= 0:
            return []
        resultExclusiveOR = 0
        length = len(array)
        for i in array:
            resultExclusiveOR ^= i
        firstBitIs1 = self.FindFisrtBitIs1(resultExclusiveOR)
        num1, num2 = 0, 0
        for i in array:
            if self.BitIs1(i, firstBitIs1):
                num1 ^= i
            else:
                num2 ^= i
        return num1, num2
        
    def FindFisrtBitIs1(self, num):
        indexBit = 0
        while num & 1 == 0 and indexBit <= 32:
            indexBit += 1
            num = num >> 1
        return indexBit
    
    def BitIs1(self, num, indexBit):
        num = num >> indexBit
        return num & 1

看到python排名第一的
**解:4：**思路是迭代，化为每个元素，在两两合并，含有合并后再在组间删除相同的元素后组成一个集合，直到所有比完，输出结果

# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        return list(self.dc(array, 0, len(array)-1))
         
    def dc(self, array, start, end):
        res = set()
        if start > end:
            return res
        if start == end:
            return set(array[start:end+1])
         
        spl = (start+end)/2
         
        s1 = self.dc(array, start, spl)
        s2 = self.dc(array, spl+1, end)
         
        return s1.union(s2).difference(s1.intersection(s2))