python實現陣列平移K位問題

2023-11-01 10:00:12

python陣列平移K位

def move(ls: list, offset):
    """
    元素原索引+位移數（正為右移，負為左移）之和求關於陣列長度（陣列的模）的餘數，即為位移後的元素索引。
    再對新索引升序排序，去除索引，即為位移後的新陣列
    :param ls:
    :param offset:
    :return:
    """
    mod = len(ls)
    ids = [[(item[0]+offset)%mod, item[1]] for item in enumerate(ls)]
    ids.sort(key=lambda item: item[0])
    return [item[1] for item in ids]

def move2(ls: list, offset):
    """
    分段反轉，以位移數（對模求餘）為界，分別反轉兩個子陣列，再整體反轉
    :param ls:
    :param offset:
    :return:
    """
    mod = len(ls)
    offset = offset % mod
    tail = list(reversed(ls[mod-offset:]))
    head = list(reversed(ls[:mod-offset]))
    return list(reversed(head+tail))

if __name__ == '__main__':
    nums = [8, 9, 10, 11]
    print(move(nums, 1))
    print(move2(nums, 1))

    print(move(nums, -1))
    print(move2(nums, -1))
    """
	[11, 8, 9, 10]
	[11, 8, 9, 10]
	[9, 10, 11, 8]
	[9, 10, 11, 8]
	"""

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

執行結果：

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

執行結果