旋轉陣列
給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數，
示例 1:
輸入:[1,2,3,4,5,6,7]和 k = 3 輸出:[5,6,7,1,2,3,4]解釋: 向右旋轉 1 步:[7,1,2,3,4,5,6]向右旋轉 2 步:[6,7,1,2,3,4,5]向右旋轉 3 步:[5,6,7,1,2,3,4]
示例 2:
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]
說明:
- 盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題，
- 要求使用空間復雜度為 O(1) 的 原地 演算法，
解答
方案1
一個一個旋轉
旋轉陣列是一個 進佇列 出佇列 動作，用下標來控制進出順序
k是要移動的次數，輸入陣列的長度是隊的長度，長度減去次數就是元素將要移動到位置的下標地址
k要對長度取余不出錯
class Solution: def rotate(self, nums, k): """ Do not return anything, modify nums in-place instead. """ temp = [] l = len(nums) k = k%l for i in range(l): temp.append(nums[(i-k)]) nums[:] = temp
方案2
串列鏈接 陣列分成兩部分重新合并，
class Solution(object): def rotate(self, nums, k):
"""
Do not return anything, modify nums in-place instead.
"""
k = k%len(nums)
nums[:] = nums[-k:]+nums[:-k]
方案3
使用佇列
class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ for _ in range(k): nums.insert(0, nums.pop())
前一個自己撰寫，后兩個https://www.jianshu.com/p/cf413a3f120a的作者撰寫
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162026.html
標籤：Python
下一篇：Celery配置及使用