Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]

Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]

Output: 8

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

描述

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]

输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]

输出: 8

说明:

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路

1.异或运算

• 亦或运算.
• 由于亦或运算相同为0，不同为1，那么一个数字自己和自己做异或运算结果为0，即偶数个相同的数亦或为0，奇数个相同的数亦或为本身.
• 给定的数从0到n一共n个数（丢失了一个），我们在加一个辅助变量i从0到n，让给定的所有数和0到n的所有数字做亦或运算，则相同的数两两配对亦或为0，丢失的数只会在i中出现了一次，于是会被保留.
• 为了方便，我们让i从0到n-1,另res初始化为n，所以结果 res = nums[0] ^ nums[1] ... ^ nums[n-1] ^0 ^1 ^ ...^n,即 res ^= nums[0] ^nums[1] ... ^nums[n-1] ^0 1...n-1'

2.求和

• 0到n的和为n*(n+1)/2,用这个和与原数组的和做差记为缺少的数字.

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-04 15:30:54
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-04 16:05:54
class Solution:
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return len(nums) * (len(nums) + 1) // 2 - sum(nums)
    def missingNumber2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 位运算  0^0^1^2^2^3^3^4^4 = 1
        # 即偶数次亦或结果为0，奇数次为本身
        # 给定的数范围从0到n共n个（丢失了一个），我们然i从0自增到n-1，另res初始化为n。
        # 对所有的数进行异或运算，重复出现的数字两两配对，抑或的结果为0
        # 落单的数字亦或会被保留
        res = len(nums)
        for i in range(len(nums)):
            res ^= i ^ nums[i]
        return res

源代码文件在这里.