n个元素的数组向左循环移动i个位置

Question

n个元素的数组向左循环移动i个位置
解法一:
先将数组前i个元素存在临时数组,在将余下的n-i个元素左移i个位置,最后将临时数组中的元素复制到后面i个位置

复杂度:
需移动i+(n-i)+i = i+n 次数组单元
需i个额外存储单元

解法二:
设计一个函数将数组向左移动一个位置,然后在调用函数i次

复杂度:
需移动i*n次数组单元
只需1个额外存储单元

解法三:
AB(A代表前i个元素,B代表后n-i个元素),先将A置换,在将B置换,最后将AB置换
AB -> A-1B -> A-1B-1 -> BA

讲解每个解法的时间效率与空间效率

Answer 1

解法一:时间复杂度o(n)，空间复杂度o(n)
解法二:时间复杂度o(k*n)，空间复杂度o(1)
解法三:时间复杂度o(n)，空间复杂度o(1)