python实现数组平移K位问题
python数组平移K位
Python对数组进行循环移位
要求
对含有N个元素的数组循环右移K位，要求时间复杂度为O(N)，且只允许使用两个附加变量。
分析
方法一：蛮力法
要求将数组元素循环右移K位，只需要每次将数组中元素右移一位，循环K次即可。如原数组为abcd1234，右移4位具体移动过程为abcd1234-->4abcd123-->34abcd12-->1234abcd。
方法二：翻转法
直接上例子，对于数组序列A = [123456]，如何实现循环右移2位功能？将数组A分成两个部分A[0,N-K-1]和A[N-K,N-1]，将这两部分分别翻转，然后放在一起再翻转，具体如下：
- ①翻转1234:123456-->432156
- ②翻转56:432156-->432165
- ③翻转432165:432165-->561234
代码实现
#方法一
# -*- coding:utf-8 -*-
def rightShift(arr,k):
if arr == None:
print("参数不合法！")
return
lens = len(arr)
k %= lens #因为K不一定小于N，有可能大于等于N，当K≥N时，右移K-N与右移K位效果一样
while k != 0: #右移k位
tmp = arr[lens-1] #数组最后一个元素放入临时变量中
i = lens-1
while i > 0:
arr[i] = arr[i-1] #所有元素后移
i -= 1
arr[0] = tmp #第一个元素为初始最后一个元素的值
k -= 1
if __name__ == "__main__":
k = 4
arr = ['a','b','c','d','1','2','3','4']
rightShift(arr,k)
i = 0
while i < len(arr):
print(arr[i],end="")
i += 1
# -*- coding:utf-8 -*-
def rightShift(arr,k):
if arr == None:
print("参数不合法！")
return
lens = len(arr)
k %= lens #因为K不一定小于N，有可能大于等于N，当K≥N时，右移K-N与右移K位效果一样
while k != 0: #右移k位
tmp = arr[lens-1] #数组最后一个元素放入临时变量中
i = lens-1
while i > 0:
arr[i] = arr[i-1] #所有元素后移
i -= 1
arr[0] = tmp #第一个元素为初始最后一个元素的值
k -= 1
if __name__ == "__main__":
k = 4
arr = ['a','b','c','d','1','2','3','4']
rightShift(arr,k)
i = 0
while i < len(arr):
print(arr[i],end="")
i += 1
运行结果：
1234abcd
#方法二
def reverse(arr,start,end):
while start<end:
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start += 1
end -= 1
def rightShift(arr,k):
if arr == None:
print("参数不合法！")
return
lens = len(arr)
k %= lens
reverse(arr,0,lens-k-1)
reverse(arr,lens-k,lens-1)
reverse(arr,0,lens-1)
if __name__ == "__main__":
k = 4
arr = ['a','b','c','d','1','2','3','4']
rightShift(arr,k)
i = 0
while i < len(arr):
print(arr[i],end="")
i += 1
def reverse(arr,start,end):
while start<end:
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start += 1
end -= 1
def rightShift(arr,k):
if arr == None:
print("参数不合法！")
return
lens = len(arr)
k %= lens
reverse(arr,0,lens-k-1)
reverse(arr,lens-k,lens-1)
reverse(arr,0,lens-1)
if __name__ == "__main__":
k = 4
arr = ['a','b','c','d','1','2','3','4']
rightShift(arr,k)
i = 0
while i < len(arr):
print(arr[i],end="")
i += 1
运行结果
1234abcd
性能分析
方法一每移动一次，其时间复杂度为O(N)，故移动K次，总的时间复杂度为O(K*N)，0<K<N，且时间复杂度不满足O(N)。
方法二时间复杂度为O(N)，完成翻转操作只用了一个辅助存储空间。
本站大部分文章、数据、图片均来自互联网,一切版权均归源网站或源作者所有。
如果侵犯了您的权益请来信告知我们删除。邮箱：1451803763@qq.com