[Leetcode] Rotate Array 旋轉數組

alighters 發布于2019-08-14 12:26 / 1152人閱讀

摘要：反轉法復雜度時間空間思路通過三次反轉，我們可以很巧妙的實現旋轉數組。首先我們將整個數組反轉，然后將前個數字反轉，然后再將后面剩下的數字反轉，就得到目標數組了。而左旋時，我們是將其后個多帶帶反轉，然后前面的多帶帶反轉。

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

雙數組 復雜度

時間 O(N) 空間 O(N)

思路

建立一個新數組，將位移過的數字放在新的數組中。

反轉法 復雜度

時間 O(N) 空間 O(1)

思路

通過三次反轉，我們可以很巧妙的實現旋轉數組。首先我們將整個數組反轉，然后將前k個數字反轉，然后再將后面剩下的數字反轉，就得到目標數組了。

注意

反轉數組最簡單的方法是交換元素，而交換元素有至少三種方法（臨時變量，相加相減，異或）

k可能大于數組長度，旋轉不止一次，所以我們要先對k取余

代碼

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);
    }
    
    private void reverse(int[] nums, int i, int j){
        while(i
后續 Follow Up
Q：如果是向左旋轉k位而不是向右呢？
A：還是同樣的方法，只是之前在反轉完整個數組后，將其前k個多帶帶反轉，后面的多帶帶反轉。而左旋時，我們是將其后k個多帶帶反轉，然后前面的多帶帶反轉。

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64479.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 189：旋轉數組 Rotate Array

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

zhangrxiang 2019-07-31 11:26 評論0 收藏0
leetcode396. Rotate Function

摘要：題目要求代表對數組在位置上進行順時針的旋轉后生成的數組。暴力循環按照題目的要求，執行兩次循環即可以獲得的所有值，只需要從中比較最大值即可。題目要求 Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k p...

yintaolaowanzi 2019-08-16 13:50 評論0 收藏0
leetcode48 Rotate Image 90度旋轉數組

摘要：每一次的旋轉，其實都是正方形上的四個元素之間的相互替換。所以本質上我們只需遍歷每種長度正方形上的一條邊，就可以完成這個正方形的旋轉。最后實現整個數組矩陣的旋轉代表正方形的起始位置，即，，即，代表當前正方形上的一條邊上的一個點。題目要求 You are given an n x n 2D matrix representing an image. Rotate the image b...

melody_lql 2019-08-16 10:34 評論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