LintCode 寻找缺失的数

本文主要是介绍LintCode 寻找缺失的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。

样例
N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。

题目说的不是很清楚，意思就是如下：
给定给一个序列，有N个数，对于{0,1,2，……N}这个N+1个数的序列中，少了哪一个数？

这道题和LintCode上另一道题类似——《落单的数》

给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

样例
给出 [1,2,2,1,3,4,3]，返回 4

解答：
利用异或运算。a⊕a=0,a⊕b=b⊕a，a⊕b⊕c=（a⊕b）⊕c=a⊕（b⊕c）
两道题代码分别如下：
落单的数：

class Solution:"""@param: A: An integer array@return: An integer"""def singleNumber(self, A):# write your code heren=len(A)if n==0:return 0result=A[0]for i in range(1,n):result=result^A[i]return result

寻找缺失的数：

class Solution:# @param nums: a list of integers# @return: an integerdef findMissing(self, nums):# write your code hereresult=0n=len(nums)for i in range(n):result=result^nums[i]^iresult=result^nreturn result

这篇关于LintCode 寻找缺失的数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---