LeetCode 189. Rotate Array

原题链接在这里：https://leetcode.com/problems/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].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

题解：

Reverse the whole array[0, n-1], then reverse [0, k-1] and [k, n-1].

Time Complexity: O(n). Space: O(1).

AC Java:

public class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return;
        }
        int len = nums.length;
        k = k%len;
        reverse(nums, 0, len-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, len-1);
    }
    
    private void reverse(int [] nums, int i, int j){
        while(i < j){
            swap(nums, i++, j--);
        }
    }
    private void swap(int [] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Method 1 新建一个array res, 找出rotate 后array 和 原来array 的位置对应关系是  res[i] = nums[(i+len-k) % len]. 最后把res 赋值回 nums.

Time Complexity: O(n). Space: O(n).

Method 2 每次只rotate 一个位置，一共循环k次。可以不用额外空间，但也用了更多的时间。

Time Complexity: O(k*n). Space: O(1).

Method 3 先reverse全部array, 在以k为分界点，分别reverse 前半部分[0, k-1], 后半部分[k, len-1]. 三种方法都需要注意k = k%len.

Time Complexity: O(n). Space: O(1).

public class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        
        /*
        //Method 1, takes O(n) space, running in O(n) time
        
        int[] res = new int[len];
        
        for(int i = 0;i<len;i++){
            res[i] = nums[(i+len-k)%len];
        }
        
        for(int i = 0;i<len;i++){
            nums[i] = res[i];
        }
         */
        
        /*
        //Method 2, takes O(k*n) time
         
         while(k>0){
             int temp = nums[len - 1];
            for(int i = len-1;i>0;i--)
            {
                nums[i] = nums[i-1];
            }
            nums[0] = temp;
            
            k--;
         }
         */
         
         //Method 3, reverse the whole array, cut it into two parts, reverse each of them
         reverse(nums, 0, len-1);
         reverse(nums, 0, k-1);
         reverse(nums, k, len-1);
    }
    
    private void reverse(int[] arr, int left, int right){
        while(left<right){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

类似Rotate List, Reverse Words in a String II.