Codility PermCheck in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 2 Minutes
  • 2017年6月2日

算法复杂度分析

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