数组中只出现一次的两个数字【python】

绝地灬酷狼 2022-04-02 03:02 236阅读 0赞

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

--------------------

首先考虑，如果一个数组出了一个数字外，其余的数组都出现了偶数次的解法：XOR异或方法可以消除偶数出现的数字  
将数组中所有的数字全部异或，得到最后的结果就是出现一次的数字

class Solution:
        def FindNumsAppearOnce(self, array):
            # write code here
            result = 0
            for i in array:
                result = result ^ i
            return result

--------------------

解法1：数组中出现两次的数字，可以用字典的算法：  
创建字典的方法：if i not in dic: dic\[i\] = 1

class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            if array == []:
                return []
            dic = { }
            for i in array:
                if i in dic:
                    dic[i] += 1
                else:
                    dic[i] = 1
            result = []
            for j in dic:
                if dic[j] == 1:
                    result.append(j)
            return result

运行时间：28ms

占用内存：5728k

解法2：可以采用array.count方法，这样时间复杂度肯定比较大。

class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            if array == []:
                return []
            result = []
            for i in array:
                if array.count(i) == 1 and i not in result:
                    result.append(i)
            return result

运行时间：29ms

占用内存：5860k