1.22 Rotate Array

Description

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.

Method

firstly: how to rotated n elements to right by k steps Eg : 1 2 3 4 5 6 7 2 3 1 5 6 7 3 1 2 6 7 1 2 3 7 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4

 rotated every elements to right by k steps 

method one: so if k == n.length then no changes k = k % length; after roatated the last element must at position k - 1 so the original first n - k elements start at k, while k elements after n - k in original array start at 0 we can split the function into three parts: first reverse all array seconde reverse first k elements, and then reverse remain n - k elments

Method two: think stragiht just move each elements to next k position, if it back to some position already has been moved, it jump to next start;

Method Three: Normal Way , copy and move

Time and Space Complexity

one : time o(n) space o(1)

two : time o(n) space o(1)

three : time o(n) space o(k % n)

Code

method one: public class Solution { // method one : reverse all array, and then reverse the k / n - k individually

   public void rotate(int[] nums, int k) {
       if (nums == null || nums.length == 0 || k == 0){
           return;
       }
       int len = nums.length;
       k = k % len;
       helper(nums, 0, len - 1);
       helper(nums, 0, k - 1);
       helper(nums, k, len - 1);
}

private void helper(int[] nums, int l, int r){
        while (l < r){
               int tmp = nums[l];
               nums[l] = nums[r];
               nums[r] = tmp;
               r--;
               l++;
        }
}
// method two

}

method two:

 public void rotate(int[] nums, int k){
          if (nums == null || nums.length <= 1){
          return;
          }
          int len = nums.length;
          k = k % len;
          if (k <= 0){
              return;
          }
          int index = k, head = 0, cur = nums[0];
          for (int i = 0; i < len; i++){
               if (index == head){
                   nums[index] = cur;
                   head++;
                   cur = nums[head];
                   index = (head + k) % len;
               } else {
                   int tmp = nums[index];
                   nums[index] = cur;
                   cur = tmp;
                   index = (index + k) % len; 
               }
          }

   }

method three:

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