LeetCode 268 MissingNumber 复杂度限制

本来想用C++写的，但是写的过程中发现很多语法都记不清了，索性转回Python，c++以后再练吧

问题描述：

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?

思路：

一个没有miss_num的数列，他的和是等差数列和 total_sum = max*（max+1）/2

那么在一个有miss_num的数列nums中，miss_num的值就是total_sum-sum(nums)

代码：

class Solution(object):

def missingNumber(self, nums):

    n = len(nums)

        sum = (n+1)*n/2

        for i in nums:

            sum -= i

        return sum

 

通过交流，发现了另一种复杂度更低的算法：

亦或运算有“两个相同的数做亦或运算为0”的性质，那么构造一个没有miss_num的数列跟原始数列做亦或就会得出那个miss_num

代码：

class Solution(object):

    def missingNumber(self, nums):

        num = 0

        l = len(nums)

        for i in nums:

            num ^= i

        for i in range(l+1):

            num ^= i

        return num

 

通过比较，第一种方法的runtime是69ms，第二种runtime是64ms