欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

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

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

相关标签: leetcode