剑指offer40-数组中只出现一次的数字

题目描述

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

知识点回顾

位运算、哈希

代码

解法一：暴力解题，双重循环，O(N^2)

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        a=[]
        for i in range(len(array)):
            flag=1
            for j in range(len(array)):
                if j!=i and array[j]==array[i]:
                    flag=0
            if flag:
                a.append(array[i])
        return a

 解法二：利用字典保存元素出现次数，最后选出字典中value为1的key返回,O(2N)

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        a={}
        for i in range(len(array)):
            try:
                a[array[i]]+=1
            except:
                a[array[i]]=1
        b=[]
        for i in a:
            if a[i]==1:
                b.append(i)
        return b

解法二改进:由于一个整型数组里除了两个数字之外，其他的数字都出现了两次。当字典中有某个key时，删除这个key，否则这个key的value为1插入字典，时间复杂度为O(N)

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        a={}
        for i in range(len(array)):
            try:
                a.pop(array[i])
            except:
                a[array[i]]=1
        return a.keys()

解法三：位运算(略)