Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
先介绍一下Python中的异或操作：
异或运算：A与B不同为1时，A、B的预算结果才为1，否则为0 （运算符：^）
异或交换原理: 数字A异或B两次，就得到A。而B被A异或两次，就得到B
任意数与自己异或操作都是0，任意数与0异或操作都得到本身。
思路:是再创建一个n个元素的列表，与提供的相加，问题就转化为在一个列表中，除了一个元素只出现一次之外，其余的都出现两次，然后找出这个只出现一次的元素。
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp = nums + list(range(len(nums)+1))
result = 0
for ele in temp:
result = result^ele
return result
if __name__ == '__main__':
sol = Solution()
nums = [0, 1, 3]
print sol.missingNumber(nums)
nums = [0]
print sol.missingNumber(nums)
nums = [1]
print sol.missingNumber(nums)
nums = [0, 1, 2, 3, 4, 5, 6]
print sol.missingNumber(nums)
别人家的思路：
1. 数字A异或B两次，就得到A
def missingNumber2(self, nums):
result = 0
for i in range(len(nums)+1):
result = result^i
for num in nums:
result ^= num
return result
2. Sort and then Binary Search
def missingNumber3(self, nums):
nums.sort()
left = 0
right = len(nums)
while(left <=right):
mid = (left+right)/2
if nums[mid] > mid:
right = mid - 1
else:
left = mid + 1
return left
