Leetcode簡單題189旋轉數組解及優化過程

離上一次許下目标好好學習努力寫文章好像已經很久了，然而我卻一直都在摸魚（悲），先自我檢讨一下，我好鹹魚。

近期終于有了點動力想提升自己，順便寫點東西記錄一下，雖然不知道這份勁頭能持續多久就是了，反正先寫着吧。

好久沒學習了，一時之間還真不知道從何下手，最後我決定先去随便刷刷Leetcode題，剩下的就找自己喜歡的書看吧。

剛開始刷我不打算刷多難的，是以選了簡單的Top Interview Questions集合（沒錯我就是這麼鹹魚）。

這裡用文章記一下第189題Rotate String的解題過程。

首先上題目連結

題目：給定一個數組，将數組中的元素向右移動 

k

 個位置，其中 

k

 是非負數。

進階：

• 盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題。
• 你可以使用空間複雜度為 O(1) 的 原地 算法解決這個問題嗎？

連結：https://leetcode.com/problems/rotate-array/solution/

一眼看去，題目看起來十分簡單，事實上也的确很簡單，甚至可以用暴力解法直接真的一個一個移動過去。

那直接先來一份暴力解法代碼

public void rotate(int[] nums, int k) {
    int temp = 0;
    for(int i = 0; i < k; i++){
        temp =  nums[nums.length-1];
        for(int m = nums.length-1; m > 0; m--){
            nums[m] = nums[m-1];
        }
        nums[0] = temp;
    }
}
           

完事，送出，運作

很好，運作速度擊敗12.27%的人，使用記憶體擊敗25.64的人，果然暴力不可取（笑）。

現在試着優化一下，既然是向右移動，那如果移動的次數超過數組大小的話，實際上是有很多無效移動的，畢竟已經轉了一圈了。

比如數組大小為5，k為31，相當于數組原地轉了6圈，實際有效移動次數就1。大小為1的數組也可以不用考慮。出于以上考慮，在

代碼最前面加上

if(nums.length<2){
    return;
}if(k>nums.length){
    k = k%nums.length;
}
           

再次運作

很好，有進步，占用記憶體好了很多，速度也提升了一點點，雖然依舊很拉跨。

寫完了暴力解法該用點正常寫法了，最簡單的當然是直接使用新的數組去存要移動的值，再填回到移動後的位置就好了。

用這個思路，寫了一個使用兩個數組去存需要移動值的代碼，這裡用了兩個數組，一個用來存從左邊移動到右邊的塊，一

個用來存從右邊移動到左邊的塊，其實是有點多餘的。

public void rotate(int[] nums, int k) {
    if(nums.length<2){
       return;
    }
    if(k>nums.length){
        k = k%nums.length;
    }
    int[] temp = new int[k];
    int[] temp2 = new int[nums.length-k];
    for(int i = 0; i < nums.length;i++){
        if(i<k){
            temp[i] = nums[nums.length-k+i];
        }else{
            temp2[i-k] = nums[i-k];
        }
    }
    for(int i = 0 ; i<nums.length ; i++){
        if(i<k){
            nums[i] = temp[i];
        }else{
            nums[i] = temp2[i-k];
        }
    }
}
           

送出，運作

運作速度和記憶體都在中間位置，看起來不至于太差勁了，但是還是不太行，上面也說到了其實用兩個數組去存是有些多餘的，用

一個去存右邊需要移動到左邊的值就可以了，剩下左側的可以在數組内向右移動到數組尾部。

稍微修改一下上面的代碼

public void rotate(int[] nums, int k) {
    if(nums.length<2){
        return;
    }
    if(k>nums.length){
        k = k%nums.length;
    }
    int[] temp = new int[k];
    for(int i = 0; i < k;i++){
        temp[i] = nums[nums.length-k+i];
    }
    for(int i = nums.length-1; i >= k;i--){
        nums[i] = nums[i-k];
    }
    for(int i = 0;i<k;i++){
        nums[i] = temp[i];
    }
}
           

這次隻用了一個額外數組

運作看看

這次的結果看起來就很不錯了，但是畢竟還是使用了一個輔助數組，沒有使用空間複雜度為 O(1) 的 原地 算法解決這個問題，不過今天就先寫到這裡吧，剩下的下次再說（大概下次一定）。