pythontip 100days-day34

移动数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数,要求使用空间复杂度为 O(1) 的原地算法

例子

move_ele([1,2,3,4,5,6,7],3) -> [5,6,7,1,2,3,4]

假设

  1. 输入参数均合法

tips

  1. 将输入数组翻转两次

解法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)