Leetcode 268. Missing Number，run time complexity

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

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

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

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

感谢lz分享！！！

ff-tt 发表于 2019-7-10 11:15
个人觉得第二种方法并不是最优的.

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

大佬能想到这样的方法，机智！len(list) 是O(1)，所以这个最后就是O(1)？

Echooogo 发表于 2019-7-12 17:06
大佬能想到这样的方法，机智！len(list) 是O(1)，所以这个最后就是O(1)？

应该是O(n)

ff-tt 发表于 2019-7-13 02:32
应该是O(n)

不好意思我有点菜，为啥是O(n) 呢？

Echooogo 发表于 2019-7-13 08:13
不好意思我有点菜，为啥是O(n) 呢？

len()是O(1), sum是O(n), 所以最后是O(n)吧。我感觉。

ff-tt 发表于 2019-7-13 08:22
len()是O(1), sum是O(n), 所以最后是O(n)吧。我感觉。

哦哦，现在理解了~~！回头看了一下公式，有 sum(nums)， 所以是O(n)
机智

第一个方法是O(n^2)。当inputsize比较大的的时候就会超时

charleskaka 发表于 2019-7-15 18:36
第一个方法是O(n^2)。当inputsize比较大的的时候就会超时

嗯嗯，对，开始用leetcode之后才开始意识到逻辑的重要性。
然后并且发现，print会很拖慢运行速度