首页 > 代码库 > LintCode Python 简单级题目 82.落单的数
LintCode Python 简单级题目 82.落单的数
题目描述：
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
您在真实的面试中是否遇到过这个题？
Yes
样例
给出 [1,2,2,1,3,4,3]，返回 4
挑战
一次遍历，常数级的额外空间复杂度
标签
贪心
题目分析：
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
利用 n^n = 0的特性，一个数异或本身结果为0
而 n^0 = n，所以 n^n-1^n = n-1，
所以保存异或结果，循环异或列表元素即可。
最后的结果就是落单的数 x
源码：
class Solution:
"""
@param A : an integer array
@return : a integer
"""
def singleNumber(self, A):
# write your code here
EOR = 0
for item in A:
# 使用异或,相同的数异或为0,与先后顺序无关
EOR = EOR^item
return EOR
LintCode Python 简单级题目 82.落单的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。