python实现找出数组中出现奇数次的数
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
下一篇: Python入门零基础
推荐阅读
-
【剑指Offer】 40.数组中只出现一次的数字 python实现
-
【剑指Offer】40. Python实现数组中只出现一次的数字
-
【剑指Offer】40.数组中只出现一次的数字(Python实现)
-
c语言和Java语言实现,两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的两个整数 - python实现
-
python实现给定一个数和数组,求数组中两数之和为给定的数
-
LeetCode [Python]1. 两数之和给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
Python实现找出数组中第2大数字的方法示例
-
python实现找出数组中丢失的数
-
python实现找出数组中出现奇数次的数