#189 Rotate Array

問題描述:

可以想一下，k值只是中間一個分水嶺，k代表index[k]位置放入nums[0]，一直往右到nums的最大index位置後，再從index[0]位置放num[i]，舉例:以k=3為例，就是index[3]位置要放入原nums[0]。而index[4]位置 要放入原nums[1]。

a= [1,2,3,4,5,6,7] k = 3.

要輸出[5,6,7,1,2,3,4]

解題思路:

let a= [1,2,3,4,5,6,7]
k = 3.

1. we have to first reverse the whole array by swapping first element with the last one and so on.. you will get[7,6,5,4,3,2,1]

2. reverse the elements from 0 to k-1 reverse the elements 7,6,5 you will get [5,6,7,4,3,2,1]

3. reverse the elements from k to n-1 reverse the elements 4,3,2,1 you will get[5,6,7,1,2,3,4]

程式碼:

class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length < 2){
            return;    
        }
        // This is to contain outOfBounds exception for K > nums.length , avoid K > nums.length
        k = k % nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);           
    }
        
    
    public void reverse(int[] arr, int start, int end){
        int temp = 0;
        while(start < end){
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

細節:

這裡爲何要做這是因為有可能發生 k > nums.length 的情況發生。如k=11, k%nums.length = 4 , k = 4

k %= nums.length;