LeetCode 189: Rotate Array (Java)

Airmusic 發(fā)布于2019-08-14 15:51 / 549人閱讀

摘要：解法一假設數組為先把換到的位置，把拿著換到的位置，把拿著換到的位置。。。停止條件姑且假設為當置換的數回到數組的首位。不過換一個栗子上述方法就不通了，比如數組為換一輪發(fā)現(xiàn)結果是。

題目： 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].

兩種解法：

第一種是原地swap，記錄下被擠掉的數再接著swap，需要一些時間舉栗子探索規(guī)律；

第二種是倒三次的方法，如果之前沒有準備過，面試中不太可能自己想出來。

解法一（12%）：

假設數組為[1,3,5,7,9], k = 2 :
先把1換到5的位置，把5拿著換到9的位置，把9拿著換到3的位置。。。最后7到了1的位置就換完了，貌似計劃通啊。
停止條件姑且假設為當置換的數回到數組的首位。
不過換一個栗子上述方法就不通了，比如數組為[1,3,5,7,9,11], k = 2, 換一輪發(fā)現(xiàn)結果是[9,3,1,7,5,11]。
這里要從3開始重復一遍上述方法，所以要再套一個loop，i = 0, 停止條件為最大公約數(數組長度,k)。這樣所有的情況都能cover了。

public static void rotate(int[] nums, int k) {
    if(nums == null || nums.length <= 1)
        return;
    k = k%nums.length;

    int prev = 0;
    int next = 0;
    int maxComm = maxCommonDivisor(k,nums.length);
    for(int i = 0; i < maxComm;i++){

        prev = nums[i];
        int j = i+k;
        j %= nums.length;
        while(j != i){
            next = nums[j];
            nums[j] = prev;
            prev = next;
            j+=k;
            j%=nums.length;
        }
        nums[j] = prev;
    }
    return;
}

private static int maxCommonDivisor(int m, int n){
    while (m % n != 0) {
        int temp = m % n;
        m = n;
        n = temp;
    }
    return n;
}

解法二（12%）：

巧妙的reverse三次：
第一次reverse整個數組；
第二次reverse子數組(0，k-1);
第三次reverse子數組(k,length-1)

reverse的函數都是一樣的，所以可以寫一個helper。

public static void rotate(int[] nums,int k) {
    if(nums == null || nums.length <= 1)
        return;
    k %=nums.length;
    if(k == 0)
        return;
    helper(nums,0,nums.length-1);
    helper(nums,0,k-1);
    helper(nums,k,nums.length-1);
}

public static void helper(int[] nums,int start,int end) {
    for(int i = start; i <= (end+start)/2;i++) {
        int temp = nums[end+start-i];
        nums[end+start-i] = nums[i];
        nums[i] = temp;
    }
}

最后貼一下最快的code（98%）：

public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k%n;
        int[] temp = Arrays.copyOfRange(nums, 0, n-k);
        System.arraycopy(nums, n-k, nums, 0, k);
        System.arraycopy(temp, 0, nums, k, n-k);
    }

Reference： 0ms 5-line java

GPU云服務器云服務器 java上array Rotate 旋轉-rotate LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66064.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
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 61：旋轉鏈表 Rotate List

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

Hwg 2019-07-31 11:30 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0