注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
求问各位大神,在刷题的时候,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)理论上来说会花更久的时间。
|