Codility PermMissingElem in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 1 Minutes
  • 2017年5月31日

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

可以想象有一个数组长度为N+1,数组元素为1,2,…N,N+1,这样便可以用等差求和公式算出该数组的总和。用总和减去输入数组A的和便可以知道数组A缺失了哪个元素。注意python sum()的算法复杂度为O(N),故该算法的算法复杂度是O(N)。

源代码

1
2
3
4
5
6
def solution(A):
# write your code in Python 2.7
N = len(A)
start = 1
end = len(A)+1
return (N+1)*(start+end)/2 - sum(A)