移动数组
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数,要求使用空间复杂度为 O(1) 的原地算法
例子
move_ele([1,2,3,4,5,6,7],3) -> [5,6,7,1,2,3,4]
假设
- 输入参数均合法
tips
- 将输入数组翻转两次
解法1:
def move_ele(lst: list, k: int) -> list:
"""
1. 控制右边k个元素,放在列表左边
2. 使用pop()弹出元素,然后使用append()追加元素
:param lst:
:param k:
:return:
"""
if not lst:
return lst
for _ in range(k + 1):
lst.append(lst.pop(0))
return lst
解法2:
def changxy(lst: list, start: int, end: int):
"""
列表在范围内翻转
:param lst:
:param start:
:param end:
:return:
"""
# 判断结束位置是否越界
end = end - 1 if end == len(lst) else end
i, j = start, end
while i <= j:
lst[i], lst[j] = lst[j], lst[i]
i += 1
j -= 1
def move_ele(lst: list, k: int) -> list:
"""
1. 前后两部分旋转
2. 整体旋转
:param lst:
:param k:
:return:
"""
# 前后两部分旋转
changxy(lst, 0, len(lst) - k - 1) # lst[:len(lst)-k]
changxy(lst, len(lst) - k, len(lst)) # lst[-k:]
print(lst)
# 整体旋转
changxy(lst, 0, len(lst))
print(lst)