Codility CyclicRotation in Python

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

算法复杂度分析

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

算法分析

并不是要真的右移K次数组,K对N取模,可求出实际要右移的次数K = K%N。利用python数组切片操作,以N-k为切点,将数组分成前后两部分,颠倒前后顺序拼接后便可得到右移K次的数组。

Pyhton数据切片

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

源代码

1
2
3
4
5
6
7
8
9
10
def solution(A, K):
# write your code in Python 2.7
# N number of array A
N = len(A)
if (N == 0):
return A
K = K%N
first = A[N-K:]
last = A[:N-K]
return first+last

参考