[python3] 56 数组中只出现一次的数字

代码涉及的python3和python2之间的区别仅仅在于print函数是否有括号，在牛客网的python2环境下不需要print任何输出，因此不影响。

题目描述

方法一：使用python内collections模块的Counter函数

#使用python内collections模块的Counter函数
# -*- coding:utf-8 -*-
import collections
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        resultList = []
        key_dict = {}
        key_dict = collections.Counter(array)
        for key, value in key_dict.items():
            if value == 1:
                resultList.append(key)
        return resultList

当然，剑指offer上还有另外一个条件：要求时间复杂度是o(n), 空间复杂度是o(1)。上面的程序需要一个额外的字典来存储每个字母出现的次数，因此明显不符合空间复杂度o(1)的要求。

方法二：使用位运算

对于这个问题，我们先考虑一个简化版的假设。若一个整形数组里，除了一个数字，其它数字都出现了两次，请找出这个只出现一次的数字。此时，可以用异或的思维，使得所有出现两次的数字在异或操作中变成0.

因此，本题将数组分成两个子数组，使得每个子数组中只包含一个只出现一次的数字。那么如何将数组分成两个我们想要的子数组呢？

若我们将原数组的所有元素都进行异或操作，那么结果肯定是不相同的那两个元素的异或结果（如[1, 2, 4, 6, 2, 1]，异或结果为0000 0100 ^ 0000 0110 = 0000 0010 = 2），说明不相同的两个元素在倒数第二位一定不同（一个1另一个是0），因此可以按照这一位的数字将原数组分成两个子数组，第一个子数组中倒数第二位是1，第二个子数组中倒数第二位是0。当然异或结果可能不止一个1，可以从前往后数以第一个1来划分，也可以从后往前数。由于相同的两个元素倒数第二位一定相同，因此相同的两个元素肯定在同一个子数组里。

接下来的代码以{2, 4, 3, 6, 3, 2, 5, 5}为例，不相同的两位数字是4， 6，异或结果为0000 0010，因此以倒数第二位为标准，将原数组中的所有元素分为两个子数组。第一个子数组的倒数第二位是1，{2, 2, 3, 3, 6}, 第二个子数组的倒数第二位是0， {4， 5， 5}。

class Solution:
    # 返回[a, b], 其中a ,b 是其中只出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        outputRes = []
        arrayOfOne = [] 
        arrayOfZero = []
        temp = array[0]
        flagNum = 1
        # 循环，使得整个数组的每个元素都参与异或，从而凸显出只出现一次的两个元素的异或值
        for i in range(1, len(array)):
            temp ^= array[i] #循环完成之后的temp，即为有标志位的二进制数, 依据其中1的位置将数组分为两个子数组
        #print("temp = ", temp)
        #构造只有一个1的二进制数，这个1和temp中右起第一个1位置一致
        flagNum = temp & (-temp)
        #print("flagNum = ", bin(flagNum))
        #划分两个子数组，分别让每个元素都和构造的有标志位的二进制数进行按位与操作
        for j in range(0, len(array)):
            if array[j] & flagNum == 0:
                arrayOfZero.append(array[j])
            else:
                arrayOfOne.append(array[j])
        #print(arrayOfZero)
        #print(arrayOfOne)
        # 此时已经将原数组按照标志位分成了两个子数组
        temp = arrayOfZero[0]
        for m in range(1, len(arrayOfZero)):
            #print(arrayOfZero[m])
            temp ^= arrayOfZero[m]
        #print("temp = ", temp)
        outputRes.append(temp)
        temp = arrayOfOne[0]
        for n in range(1, len(arrayOfOne)):
            temp ^= arrayOfOne[n]
        outputRes.append(temp)
        return outputRes

通过啦~

但是这里用了两个额外的数组来存储两个子数组，可以省略掉存储子数组这一步，直接计算子数组的异或值。具体代码如下：

class Solution:
    # 返回[a, b], 其中a ,b 是其中只出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        outputRes = []
        arrayOfOne = [] 
        arrayOfZero = []
        outputA = 0
        outputB = 0
        temp = array[0]
        flagNum = 1
        # 循环，使得整个数组的每个元素都参与异或，从而凸显出只出现一次的两个元素的异或值
        for i in range(1, len(array)):
            temp ^= array[i] #循环完成之后的temp，即为有标志位的二进制数, 依据其中1的位置将数组分为两个子数组
        #print("temp = ", temp)
        #构造只有一个1的二进制数，这个1和temp中右起第一个1位置一致
        flagNum = temp & (-temp)
        #print("flagNum = ", bin(flagNum))
        #划分两个子数组，分别让每个元素都和构造的有标志位的二进制数进行按位与操作
        for j in range(0, len(array)):
            if array[j] & flagNum == 0:
                #arrayOfZero.append(array[j])
                outputB ^= array[j] #这里为outputA和outputB设置初始值为0并不影响最终的异或结果，但是不能设置为1
            else:
                #arrayOfOne.append(array[j])
                outputA ^= array[j]
        outputRes.append(outputA)
        outputRes.append(outputB)
        return outputRes

2. 修改题目

在一个数组中除一个数字只出现一次之外，其它数字都出现了三次。请找出那个只出现一次的数字。

先不考虑只出现一次的那个数字，若当前数组中所有数字都出现了3次，若以32位来表示每个数字，如下面示例。

{3, 3, 3}--二进制表示如下：
{00000000 00000000 00000000 00000011,
  00000000 00000000 00000000 00000011，
  00000000 00000000 00000000 00000011}

如果将二进制表示的每一位分别求和，则和都可以被3整除。上面3个数的和为：
  00000000 00000000 00000000 00000033

若此时有一个数字只出现了一次，
{3, 3, 3, 4}
{00000000 00000000 00000000 00000011,
  00000000 00000000 00000000 00000011，
  00000000 00000000 00000000 00000011
  00000000 00000000 00000000 00000100}, 其和为：
  00000000 00000000 00000000 00000133}
其中，倒数第一位和倒数第二位都为3，可以被3整除，说明只出现了一次的那个数字这两位都是0。倒数第三位是1， 不可以被3整除，说明只出现了一次的那个数字这一位是1。

按照以上的想法来看，代码如下：

class Solution(object):
    def FindNumAppearOnce(self, array):
        result = [0] * 32 #最后这个只出现一次的数字的二进制形式是一个字符串
        #array = list(map(bin, array))
        flag = 1
        for i in range(31, 0, -1):
            #print("flag = ", bin(flag))
            for j in range(0, len(array)):
                #print("array[%s] = %s" %(j, array[j]))
                if array[j] & flag != 0: #若当前数字当前位等于1，则给result的当前位加1
                    result[i] += 1
                    #print("result[%s] = %s" %(i, result[i]))
            flag = flag << 1
            if result[i] % 3 == 0:
                result[i] = 0
            else:
                result[i] = 1
        #print("reault = ", result)
        result = list(map(str, result))
        outputResult = "".join(result)
        print(int(outputResult, 2)) #二进制字符串转十进制，输出4

if __name__ == "__main__":
    s = Solution()
    outputRes = []
    inputArray = [3, 3, 3, 4]
    outputRes = s.FindNumAppearOnce(inputArray)