LeetCode 189. Rotate Array

Medium題。給一陣列及一非負整數，將陣列的每個元素向右移動整數個位置，右移的元素超過陣列長度則調到陣列頭部。

題目

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

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

先想到的解法

建立一個新陣列存放移動結果，用一個廽圈遍歷陣列，當索引小於位移數時，將陣列由後往前數的位移數後的元素從頭放到新陣列；當索引大於位移數時則放到新陣列位移數後的位置。時間複雜度O(n)；空間複雜度O(n)。

nums=[1,2,3,4,5,6,7]  k=3
rotatedNums=[0,0,0,0,0,0,0]
============================L1=============================
             v(i=0) < k
rotatedNums=[5,0,0,0,0,0,0]
                     v
       nums=[1,2,3,4,5,6,7]
============================L2=============================
               v(i=1) < k
rotatedNums=[5,6,0,0,0,0,0]
                       v
       nums=[1,2,3,4,5,6,7]
============================L3=============================
                 v(i=2) < k
rotatedNums=[5,6,7,0,0,0,0]
                         v
       nums=[1,2,3,4,5,6,7]
============================L4=============================
                   v(i=3) >= k
rotatedNums=[5,6,7,1,0,0,0]
             v
       nums=[1,2,3,4,5,6,7]
============================L5=============================
                     v(i=4) >= k
rotatedNums=[5,6,7,1,2,0,0]
               v
       nums=[1,2,3,4,5,6,7]
============================L6=============================
                       v(i=5) >= k
rotatedNums=[5,6,7,1,2,3,0]
                 v
       nums=[1,2,3,4,5,6,7]
============================L7=============================
                         v(i=6) >= k
rotatedNums=[5,6,7,1,2,3,4]
                   v
       nums=[1,2,3,4,5,6,7]

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3))); // [5, 6, 7, 1, 2, 3, 4]
        System.out.println(Arrays.toString(rotate(new int[]{-1, -100, 3, 99}, 2))); // [3, 99, -1, -100]
        System.out.println(Arrays.toString(rotate(new int[]{1, 2}, 5))); // [2, 1]
    }

    public static int[] rotate(int[] nums, int k) {
        k = k % nums.length;
        int[] rotatedNums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                rotatedNums[i] = nums[nums.length - k + i];
            } else {
                rotatedNums[i] = nums[i - k];
            }
        }
        System.arraycopy(rotatedNums, 0, nums, 0, rotatedNums.length);
        return nums;
    }

}

更加解

題目說至少有三種方法可解，且能只用O(1)空間複雜度在陣列內交換的解法。

參考討論區的O(1)解法如下，先將陣列翻轉，再把第一個元素到第k-1的元素翻轉，再把第k-1的元素到最後的元素翻轉。時間複雜度O(n)；空間複雜度O(1)。我想這解法是觀察翻轉結果想出來的。

           ┌────k=3────┐
           │           ▼
         ┌─┴─┬───┬───┬───┬───┬───┬───┐
         │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
         └───┴───┴───┴───┴───┴───┴───┘

step 1:reverse the whole array

         ┌───┬───┬───┬───┬───┬───┬───┐
         │ 7 │ 6 │ 5 │ 4 │ 3 │ 2 │ 1 │
         └───┴───┴───┴───┴───┴───┴───┘

step 2:reverse 0 to k-1 sub array

         ┌───┬───┬───┬───┬───┬───┬───┐
         │ 5 │ 6 │ 7 │ 4 │ 3 │ 2 │ 1 │
         └───┴───┴───┴───┴───┴───┴───┘

step 3:reverse k to end sub array

         ┌───┬───┬───┬───┬───┬───┬───┐
         │ 5 │ 6 │ 7 │ 1 │ 2 │ 3 │ 4 │
         └───┴───┴───┴───┴───┴───┴───┘

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3))); // [5, 6, 7, 1, 2, 3, 4]
        System.out.println(Arrays.toString(rotate(new int[]{-1, -100, 3, 99}, 2))); // [3, 99, -1, -100]
        System.out.println(Arrays.toString(rotate(new int[]{1, 2}, 5))); // [2, 1]
    }

    public static int[] 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);
        return nums;
    }

    public static void reverse(int[] nums, int start, int end) {
        int tmp;
        while (start < end) {
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

}

陣列反轉可參考Reverse String。