Codility CyclicRotation in Python

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

算法复杂度分析

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

  • 给切片起始、终止值和步长，
  • a[0:5:2] # [0, 2, 4]
  • 给切片起始和终止值，步长值缺省时其默认值为1
    • a[0:5] # [0, 1, 2, 3, 4]
    • a[0:] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    • a[:5] # [0, 1, 2, 3, 4]
    • a[:] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 给负值
  • a[-1] # 9
  • a[-2:] # [8, 9]
  • a[:-2] # [0, 1, 2, 3, 4, 5, 6, 7]

源代码

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

参考

  • Python数组切片算法复杂度分析
  • Python数组切片操作解释