[Leetcode] Rotate Array 旋轉(zhuǎn)數(shù)組

alighters 發(fā)布于2019-08-14 12:26 / 1157人閱讀

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

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].

雙數(shù)組 復雜度

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

思路

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

反轉(zhuǎn)法 復雜度

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

思路

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

注意

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

k可能大于數(shù)組長度，旋轉(zhuǎn)不止一次，所以我們要先對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
后續(xù) Follow Up
Q：如果是向左旋轉(zhuǎn)k位而不是向右呢？
A：還是同樣的方法，只是之前在反轉(zhuǎn)完整個數(shù)組后，將其前k個多帶帶反轉(zhuǎn)，后面的多帶帶反轉(zhuǎn)。而左旋時，我們是將其后k個多帶帶反轉(zhuǎn)，然后前面的多帶帶反轉(zhuǎn)。

云服務器 GPU云服務器旋轉(zhuǎn)-rotate 數(shù)組array 數(shù)組Array類型旋轉(zhuǎn)數(shù)組

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64479.html

LeetCode 189：旋轉(zhuǎn)數(shù)組 Rotate Array

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

cnsworder 2019-08-16 18:31 評論0 收藏0
LeetCode 189：旋轉(zhuǎn)數(shù)組 Rotate Array

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

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

摘要：題目要求代表對數(shù)組在位置上進行順時針的旋轉(zhuǎn)后生成的數(shù)組。暴力循環(huán)按照題目的要求，執(zhí)行兩次循環(huán)即可以獲得的所有值，只需要從中比較最大值即可。題目要求 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度旋轉(zhuǎn)數(shù)組

摘要：每一次的旋轉(zhuǎn)，其實都是正方形上的四個元素之間的相互替換。所以本質(zhì)上我們只需遍歷每種長度正方形上的一條邊，就可以完成這個正方形的旋轉(zhuǎn)。最后實現(xiàn)整個數(shù)組矩陣的旋轉(zhuǎn)代表正方形的起始位置，即，，即，代表當前正方形上的一條邊上的一個點。題目要求 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：旋轉(zhuǎn)鏈表 Rotate List

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

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