LeetCode 189：旋轉數組 Rotate Array

zhangrxiang 發布于2019-07-31 11:26 / 1622人閱讀

摘要：公眾號愛寫給定一個數組，將數組中的元素向右移動個位置，其中是非負數。只要截取輸入的后位的數組與輸入的剩余長度的數組，即為所求但是題目要求使用空間復雜度為的原地算法。利用切片切片組成新數組

公眾號：愛寫bug（ID：icodebugs）

給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。

Given an array, rotate the array to the right by k steps, where k is non-negative.

示例 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) 的原地算法。

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Could you do it in-place with O(1) extra space

解題思路：

? 如果按照示例那種一步一步向右移，太慢。我們直接看示例1輸入和最終結果輸出（移動步數k=3）：

輸入: [1,2,3,4,5,6,7]
輸出: [5,6,7,1,2,3,4]

找一下規律，我起先是以為直接以該索引 i 與 i+3 交換位置，不過仔細看一下就發現錯的太離譜了。

我們可以發現輸出前三位數是輸入的后三位，輸出后四位數是輸入的前四位。而移動步數 k=3，剩余長度=數組長度 - 移動步數 = 7-3=4 ，剛好對應我們發現的規律。

只要截取輸入的后k位的數組與輸入的剩余長度的數組，即為所求：[5,6,7]+[1,2,3,4]

但是：題目要求使用空間復雜度為 O(1) 的原地算法。這在python中可以利用切片特性直接像上面那樣截取，而空間復雜度不變。但是在CC++、Java里是肯定會改變空間復雜度，不滿足要求。

這時候可以換個思路，如下所示不斷反轉特定長度數組：

輸入: [1,2,3,4,5,6,7]反轉整個數組: [7,6,5,4,3,2,1]
反轉前k位：[5,6,7]
反轉剩余的: [1,2,3,4]
輸出: [5,6,7,1,2,3,4]

或者改變一下順序先反轉前剩余位數和后k位：

輸入: [1,2,3,4,5,6,7]反轉前剩余長度的: [4,3,2,1]
反轉后k位：[7,6,5]
此時數組：[4,3,2,1,7,6,5]
反轉整個數組: [5,6,7,1,2,3,4]
輸出: [5,6,7,1,2,3,4]

Java（反轉數組）：

class Solution {
    public void rotate(int[] nums, int k) {
        int numsLen=nums.length,temp;
        k=k%numsLen;
        if(k==0) return;
        swapArray(nums,0,numsLen-1);//反轉整個數組
        swapArray(nums,0,k-1);//反轉0到k-1索引，前k位的數組
        swapArray(nums,k,numsLen-1);//反轉k到末尾索引，后剩余位數位的數組
    }
    private void swapArray(int[] nums,int start,int end){//反轉函數
        int temp;
        for (int i=start,j=end;i
注：Java段代碼是以反轉方法里介紹的第一個方法為例，第二種方法只要改變一下
swapArray(nums,0,numsLen-1);//反轉整個數組
swapArray(nums,0,k-1);//反轉0到k-1索引，前k位的數組
swapArray(nums,k,numsLen-1);//反轉k到末尾索引，后剩余位數位的數組
的順序和參數即可，不再復現。
Python3（利用切片）：
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        k = k%nums_len
        nums[0:nums_len] = nums[nums_len-k:] + nums[:nums_len-k]#切片組成新數組

GPU云服務器云服務器旋轉-rotate 數組array 數組Array類型旋轉數組

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45107.html

LeetCode 189：旋轉數組 Rotate Array

摘要：公眾號愛寫給定一個數組，將數組中的元素向右移動個位置，其中是非負數。只要截取輸入的后位的數組與輸入的剩余長度的數組，即為所求但是題目要求使用空間復雜度為的原地算法。利用切片切片組成新數組公眾號：愛寫bug（ID：icodebugs）給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。 Given an array, rotate the array to the ...

cnsworder 2019-08-16 18:31 評論0 收藏0
LeetCode每日一題: 旋轉數組（No.189）

摘要：題目旋轉數組給定一個數組，將數組中的元素向右移動個位置，其中是非負數。例如將到反轉將到反轉全部翻轉得到最后結果。這里要注意下還有這樣的情況即大于數組長度的情況。次旋轉次旋轉轉回來了次旋轉次旋轉轉回來了次旋轉所以這里的有效等于對數組長度求余。題目：旋轉數組給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。示例：輸入: [1,2,3,4,5,6,7] 和 k...

FreeZinG 2019-05-22 19:46 評論0 收藏0
LeetCode 189.Rotate Array

摘要：問題描述解題思路使用數組自帶的方法和方法把數組最后一個取出來加入到頭部。使用數組的方法得到后個數，再用方法刪去后個數，最后用方法把得到的后個數添加到數組前面。問題描述： 189.Rotate Array Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, t...

leanote 2019-08-21 15:16 評論0 收藏0
LeetCode 189: Rotate Array (Java)

摘要：解法一假設數組為先把換到的位置，把拿著換到的位置，把拿著換到的位置。。。停止條件姑且假設為當置換的數回到數組的首位。不過換一個栗子上述方法就不通了，比如數組為換一輪發現結果是。題目： Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [...

Airmusic 2019-08-14 15:51 評論0 收藏0
LeetCode 61：旋轉鏈表 Rotate List

摘要：給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動個位置，其中是非負數。按上述思路解，與旋轉數組那道題大同小異，來介紹另一種很簡單高效的方法。只需在第個節點之后切斷，首尾連接即可。另外可能大于鏈表長度，應當做求余運算。 ?給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，其中 k 是非負數。 Given a linked list, rotate the list to the ...

Hwg 2019-07-31 11:30 評論0 收藏0