Leetcode 268. Missing Number，run time complexity

求问各位大神，在刷题的时候，268题，如下：
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

两种解法：
1，search 一次

[Bash shell] 纯文本查看 复制代码

def missingNumber(self, nums: List[int]) -> int:
        
        #This would cause the run time error
        for i in range (len(nums)+1):
            if i not in nums:
                return i
        

2，算正确的数组的和，与实际数组之和的差：

[Bash shell] 纯文本查看 复制代码

def missingNumber(self, nums: List[int]) -> int:
        standard_sum = 0
        for i in range (len(nums)+1):
            standard_sum+= i
        actual_sum = sum(nums)
        
        return (standard_sum-actual_sum)

为何在输入的nums 过大时，第一种解法就会 time limit exceed， 但是第二种不会？
我的理解：
第一种解法，遍历Python list一次，每次search 是O(1), 总共就是O(n),
第二种解法，算正确数组的最大和的时候，遍历一次，O(n), sum(nums): O(n), 两个之和 2*O(n)理论上来说会花更久的时间。

Echooogo 发表于 2019-7-10 08:57
好问题，不知道的说，我觉得能想到解法二的人真的挺聪明的

个人觉得第二种方法并不是最优的.

standard_num = (0+len(nums))*(len(nums)+1)／2
return standard_num - sum(nums)

上面的至少比方法二快，当初我记得我就是这么做的。
这就是我说的小学高斯公式。

这道题我前天刚做。你第一个解法的time complexity is O(n^2) since you have two for loops and each for loop iterate for n times. so is n * n = n^2. The math approach is a great choice in this scenario.

“第一种解法，遍历Python list一次，每次search 是O(1), 总共就是O(n),”

不，每次遍历是On,总共是On方

可以用exclusive or，用每个element和它对应的index做XOR最后再XOR n+1 => O(N)

mint0715 发表于 2019-7-10 05:21
“第一种解法，遍历Python list一次，每次search 是O(1), 总共就是O(n),”

不，每次遍历是On,总共是On方

谢谢大佬~~！
之后也去找了个相关的网页： https://www.ics.uci.edu/~pattis/ ... omplexitypython.txt

lilydiaz 发表于 2019-7-10 07:25
可以用exclusive or，用每个element和它对应的index做XOR最后再XOR n+1 => O(N)

谢谢~~！我刚刚去了解了一下XOR，XOR用set，然后set 的containment 是 O（1）
机智机智！！
我把相关链接放在这里，自己之后能查看，也希望能帮到别人：https://stackoverflow.com/questi ... two-lists-in-python

小学所学的高斯公式？

yongmiles 发表于 2019-7-10 08:42
小学所学的高斯公式？

好问题，不知道的说，我觉得能想到解法二的人真的挺聪明的

感谢lz分享！！！