python實現(xiàn)數(shù)組平移K位問題
更新時間：2023年02月06日 16:06:42 作者：scu-zrb
這篇文章主要介紹了python實現(xiàn)數(shù)組平移K位問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
python數(shù)組平移K位
def move(ls: list, offset):
"""
元素原索引+位移數(shù)（正為右移，負為左移）之和求關(guān)于數(shù)組長度（數(shù)組的模）的余數(shù)，即為位移后的元素索引。
再對新索引升序排序，去除索引，即為位移后的新數(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ù)（對模求余）為界，分別反轉(zhuǎn)兩個子數(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對數(shù)組進行循環(huán)移位
要求
對含有N個元素的數(shù)組循環(huán)右移K位，要求時間復(fù)雜度為O(N)，且只允許使用兩個附加變量。
分析
方法一：蠻力法
要求將數(shù)組元素循環(huán)右移K位，只需要每次將數(shù)組中元素右移一位，循環(huán)K次即可。如原數(shù)組為abcd1234，右移4位具體移動過程為abcd1234-->4abcd123-->34abcd12-->1234abcd。
方法二：翻轉(zhuǎn)法
直接上例子，對于數(shù)組序列A = [123456]，如何實現(xiàn)循環(huán)右移2位功能？將數(shù)組A分成兩個部分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
代碼實現(xiàn)
#方法一
# -*- coding:utf-8 -*-
def rightShift(arr,k):
? ? if arr == None:
? ? ? ? print("參數(shù)不合法！")
? ? ? ? return
? ? lens = len(arr)
? ? k %= lens #因為K不一定小于N，有可能大于等于N，當(dāng)K≥N時，右移K-N與右移K位效果一樣
? ? while k != 0: #右移k位
? ? ? ? tmp = arr[lens-1] #數(shù)組最后一個元素放入臨時變量中
? ? ? ? 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運行結(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運行結(jié)果
1234abcd
性能分析
方法一每移動一次，其時間復(fù)雜度為O(N)，故移動K次，總的時間復(fù)雜度為O(K*N)，0<K<N，且時間復(fù)雜度不滿足O(N)。
方法二時間復(fù)雜度為O(N)，完成翻轉(zhuǎn)操作只用了一個輔助存儲空間。
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于重構(gòu)Python代碼的六個實例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了python 實現(xiàn)倒計時功能(gui界面)，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-11-11
這篇文章主要介紹了20行代碼教你用python給證件照換底色的方法示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要為大家詳細介紹了Python繪制數(shù)碼晶體管日期，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
利用Python?Difflib庫強大的文字比較功能快速輕松查重
這篇文章主要介紹了利用Python?Difflib庫強大的文字比較功能快速輕松查重實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01
Python文件基本操作open函數(shù)應(yīng)用與示例詳解
這篇文章主要為大家介紹了Python文件基本操作open函數(shù)應(yīng)用與示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
setting配置也經(jīng)常將一些配置混淆今天主要是介紹django中的setting最佳配置小結(jié)，需要的朋友參考下吧2017-11-11
pandas修改DataFrame列名的實現(xiàn)方法
這篇文章主要介紹了pandas修改DataFrame列名的實現(xiàn)方法， 文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02
Python操作數(shù)據(jù)庫之?dāng)?shù)據(jù)庫編程接口
這篇文章主要介紹了Python操作數(shù)據(jù)庫之?dāng)?shù)據(jù)庫編程接口，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，感興趣的小伙伴可以參考一下2022-06-06
這篇文章主要介紹了python實現(xiàn)簡易云音樂播放器，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01