189. Rotate Array.md

189. Rotate Array

---

leetcode Daily Challenge on October 15th, 2020.

leetcode-cn Daily Challenge on January 8th, 2021.

---

Difficulty : Medium

Related Topics : Array

---

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

Follow up:

• 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?

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 <= 2 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

---

Solution

• mine
  • Java

    • Time Limit Exceeded

      // O(n * k)time
      // O(1)space
      public void rotate(int[] nums, int k) {
          if(k == 0 || nums == null || nums.length == 0){
              return;
          }
          int temp = 0;
          int size = nums.length;
          for(int i = 0; i < k; i++){
              temp = nums[size - 1];
              for(int j = size - 1; j > 0; j--){
                 nums[j] = nums[j - 1];
              }
              nums[0] = temp;
          }
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.4 MB, less than 12.69% of Java online submissions

      // O(N)time
      // O(1)space
      public void rotate(int[] nums, int k) {
          int n = nums.length;
          if(n == 0) return;
          k = k % n;
          if(k == 0) return;
          reverse(nums, 0, n - 1);
          reverse(nums, 0, k - 1);
          reverse(nums, k, n - 1);
      }
      
      void reverse(int[] arr, int l, int r) {
          int t;
          while (l < r) {
              t = arr[l];
              arr[l] = arr[r];
              arr[r] = t;
              l++;
              r--;
          }
      }
      

    • Runtime: 2 ms, faster than 29.04%, Memory Usage: 40.3 MB, less than 12.69% of Java online submissions

      // O(N)time
      // O(N)space
      public void rotate(int[] nums, int k) {
          if(k == 0 || nums == null || nums.length == 0){
              return;
          }
          Map<Integer,Integer> map = new HashMap<>();
          int size = nums.length;
          k = k % size;
          for(int i = 0; i < size; i++){
              map.put((i + k) % size, nums[i]);
          }
      
          for(int i = 0; i< size; i++){
              nums[i] = map.get(i);
          }
      }
      

---

• the most votes Your runtime beats 98.09 % of java submissions.

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.4 MB, less than 12.69% of Java online submissions

  // O(n)time
  // O(1)space
  public void rotate(int[] nums, int 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[] nums, int start, int end) {
      while (start < end) {
          int temp = nums[start];
          nums[start] = nums[end];
          nums[end] = temp;
          start++;
          end--;
      }
  }
  

---

• leetcode Solution

• Cyclic Replacements Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.6 MB, less than 12.69% of Java online submissions

  // O(N)time
  // O(1)space
  public void rotate(int[] nums, int k) {
      k = k % nums.length;
      int count = 0;
      for (int start = 0; count < nums.length; start++) {
          int current = start;
          int prev = nums[start];
          do {
              int next = (current + k) % nums.length;
              int temp = nums[next];
              nums[next] = prev;
              prev = temp;
              current = next;
              count++;
          } while (start != current);
      }
  }
  

---