Codility PermCheck in Python

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

算法复杂度分析

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

设输入数组长度为N，最优情况在输入数组的最大值不等于N时达成

算法分析

permutation 被定义为长为N的数组，包含整数1到N，且每个整数包含有且仅有一次。根据定义，我们必须遍历完输入数组才能知道是否1到N的每个整数包含有且仅有一次，所以算法复杂度为O(N)且无法继续优化。如何检测输入数组中1到N的每个整数出现有且仅有一次呢？一个比较直观的方法是用一个长度为N的数组作标记，遍历输入数组并在标记数组的对应项作标记，一旦该标记数组所有项均被标记，则说明输入数组满足permutation定义。但是该方法有一个缺点，就是需要成比例于输入数组长度N的存储空间。有没有不需要额外存储空间的算法呢？答案当然是有的，技巧在于利用输入数组，在遍历输入数组的同时，利用输入数组做标记。由于输入数组各项均为正整数，我们可以将某一项置为负值来标记该项索引+1对应的正整数出现过一次。

源代码

1
2
3
4
5
6
7
8
9
def solution(A):
    # write your code in Python 2.7
    for i in xrange(len(A)):
        index = A[i] if A[i] > 0 else -A[i]
        if index > len(A) or A[index - 1] < 0:
            return 0
        else:
            A[index - 1] = -A[index - 1]
    return 1