Codility PermMissingElem in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 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)