快捷導(dǎo)航

python實(shí)現(xiàn)數(shù)組平移K位問題

更新時(shí)間：2023年02月06日 16:06:42 作者：scu-zrb

這篇文章主要介紹了python實(shí)現(xiàn)數(shù)組平移K位問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

python數(shù)組平移K位

def move(ls: list, offset):
    """
    元素原索引+位移數(shù)（正為右移，負(fù)為左移）之和求關(guān)于數(shù)組長(zhǎng)度（數(shù)組的模）的余數(shù)，即為位移后的元素索引。
    再對(duì)新索引升序排序，去除索引，即為位移后的新數(shù)組
    :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):
    """
    分段反轉(zhuǎn)，以位移數(shù)（對(duì)模求余）為界，分別反轉(zhuǎn)兩個(gè)子數(shù)組，再整體反轉(zhuǎn)
    :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對(duì)數(shù)組進(jìn)行循環(huán)移位

要求

對(duì)含有N個(gè)元素的數(shù)組循環(huán)右移K位，要求時(shí)間復(fù)雜度為O(N)，且只允許使用兩個(gè)附加變量。

分析

方法一：蠻力法

要求將數(shù)組元素循環(huán)右移K位，只需要每次將數(shù)組中元素右移一位，循環(huán)K次即可。如原數(shù)組為abcd1234，右移4位具體移動(dòng)過程為abcd1234-->4abcd123-->34abcd12-->1234abcd。

方法二：翻轉(zhuǎn)法

直接上例子，對(duì)于數(shù)組序列A = [123456]，如何實(shí)現(xiàn)循環(huán)右移2位功能？將數(shù)組A分成兩個(gè)部分A[0,N-K-1]和A[N-K,N-1]，將這兩部分分別翻轉(zhuǎn)，然后放在一起再翻轉(zhuǎn)，具體如下：

①翻轉(zhuǎn)1234:123456-->432156
②翻轉(zhuǎn)56:432156-->432165
③翻轉(zhuǎn)432165:432165-->561234

代碼實(shí)現(xiàn)

#方法一
# -*- coding:utf-8 -*-
def rightShift(arr,k):
? ? if arr == None:
? ? ? ? print("參數(shù)不合法！")
? ? ? ? return
? ? lens = len(arr)
? ? k %= lens #因?yàn)镵不一定小于N，有可能大于等于N，當(dāng)K≥N時(shí)，右移K-N與右移K位效果一樣
? ? while k != 0: #右移k位
? ? ? ? tmp = arr[lens-1] #數(shù)組最后一個(gè)元素放入臨時(shí)變量中
? ? ? ? i = lens-1
? ? ? ? while i > 0:
? ? ? ? ? ? arr[i] = arr[i-1] #所有元素后移
? ? ? ? ? ? i -= 1
? ? ? ? arr[0] = tmp #第一個(gè)元素為初始最后一個(gè)元素的值
? ? ? ? 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

運(yùn)行結(jié)果：

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("參數(shù)不合法！")
? ? ? ? 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

運(yùn)行結(jié)果