189. Rotate Array

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

Example 1:
Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
**********/


/********** Solution1 **********/
class Solution {
    public void rotate(int[] nums, int k) {
        k = (nums.length + (k % nums.length)) % nums.length;
        int temp;
        
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        for (int i = 0, j = k-1; i < j; i++, j--) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        for (int i = k, j = nums.length - 1; i < j; i++, j--) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
// [1,2,3,4,5,6,7] and k = 3
// [7,6,5,4,3,2,1]
// [5,6,7,4,3,2,1]
// [5,6,7,1,2,3,4]
/********** Solution1 **********/



/********** Solution2 **********/
class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || k < 0) {
            return;
        }
        
        int temp;
        
        for (int i = 1; i <= k; i++) {
            for (int j = nums.length - 1; j > 0; j--) {
                temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
            }
        }
    }
}
// It's like bubble rotate
// i=0
// 0 1 2 3 4 5 6 
// 0 1 2 3 4 6 5
// ...
// 6 0 1 2 3 4 5
// i=1
// 6 0 1 2 3 5 4 
// ...
// 5 6 0 1 2 3 4 
// i=2
// 5 6 0 1 2 4 3 
// ...
// 4 5 6 0 1 2 3 
/********** Solution2 **********/