python实现找出数组中出现奇数次的数

题目描述:
数组中有N+2个数， 其中， N个数出现了偶数次， 2个数出现了奇数次(这两个数不相等〉，请用 0(1)的空间复杂度，找出这两个数 。 注意 : 不需要知道具体位置，只需要找出这两 个 数。
字典法
对于本题而言，定义一个字典，把数组元素的值作为 key，遍历整个数组，如果 key 值不
存在， 则将 value 设为 1，如果 key 值己经存在，则翻转该值(如果为 0，则翻转为 l;如果 为 l，则翻转为 0)，在完成数组遍历后，字典中 value为 1 的就是出现奇数次的数。

def get2Num(arr):
    if arr==None or len(arr)<1:
        print('参数不合理')
        return
    dic=dict()
    i=0
    while i<len(arr):
        if arr[i] not in dic:
            dic[arr[i]]=1
        else:
            dic[arr[i]]=0
        i+=1
    for k,v in dic.items():
        if v==1:
            print(int(k))
if __name__=='__main__':
    arr=[3,5,6,6,5,7,2,2]
    get2Num(arr)

异或法
O(n)。 但是申请了额外的存储过程来记根据异或运算的性质不难发现，任何一个数字异或它自己其结果都等于 0。 所以，对于 本题中的数组元素而言，如果从头到尾依次异或每一个元素，那么异或运算的结果自然也就 是那个只出现奇数次的数字 ， 因为出现偶数次的数字会通过异或运算全部消掉。
但是通过异或运算，也仅仅只是消除掉了所有出现偶数次数的数字，最后异或运算的结 果肯定是那两个出现了奇数次的数异或运算的结果 。 假设这两个出现奇数次的数分别为 a 与 b，根据异或运算的性质，将二者异或运算的结果记为c， 由于a与b不相等，所以， c的值自然也不会为 0，此时只需知遥 c对应的二进制数中某一个位为 l 的位数 N，例如，十进制数 44可以由二进制0010 1100表示，此时可取N=2或者3，或者5， 然后将c与数组中第N位 为1的数进行异或， 异或结果就是a, b中一个，然后用c异或其中一个数，就可以求出另外 一 个数了。
通过上述方法为什么就能得到问题的解呢?其实很简单， 因为c中第N位为 l表示a或 b中有一个数的第N位也为1，假设该数为a，那么， 当将c与数组中第N位为l的数进行异 或时， 也就是将x与a外加上其他第N位为l的出现过偶数次的数进行异或，化简即为x与 a异或，结果即为 b。
示例代码如下 :

def get2Num(arr):
    if arr==None or len(arr)<1:
        print('参数不合理')
        return 
    result=0
    position=0
    i=0
    while i<len(arr):
        result=result^arr[i]
        i+=1
    tmpResult=result
    i=result
    while i&1==0:
        position+=1
        i=i>>1
    i=1
    while i<len(arr):
        if ((arr[i]>>position)&1)==1:
            result=result^arr[i]
        i+=1
    print(result)
    print(result^tmpResult)
if __name__=='__main__':
    arr=[3,5,6,6,5,7,2,2]
    get2Num(arr)

本文地址：https://blog.csdn.net/weixin_42813521/article/details/107658605