Given an array, move the elements of the array k positions to the right, where k is non-negative.

Example 1:

,2,3,4,5,6,7 input: [1] and output: k = 3,6,7,1,2,3,4 [5] : spin to the right step 1:,1,2,3,4,5,6 [7] spin to the right step 2:,7,1,2,3,4,5 [6] to the right rotation step 3: ,6,7,1,2,3,4 [5]Copy the code

Example 2:

Input: [- 1-100,3,99] and k = 2 output: [13, 3-1-100] : step 1: rotating to the right to produce 99, 1-100 and spin to the right step 2: [13, 3-1-100]Copy the code

Description:

  • Come up with as many solutions as you can. There are at least three different ways to solve the problem.
  • The in situ algorithm with space complexity O(1) is required.

Method 1: violent solution

The simplest method is to rotate the array k times, one element at a time.

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  // Set two variables
  let temp;
  let previous;
  for (let i = 0; i < k; i++) {
    // This section fetches the last element of the array as previous
    previous = nums[nums.length - 1];
    // Inner loop
    for (let j = 0; j < nums.length; j++) {
      // Assign the current loop element to an intermediate variable using the intermediate variable continuously
      // Overwrite the previous element over the next element, so that after a round, an element is already
      // Complete the rollovertemp = nums[j]; nums[j] = previous; previous = temp; }}}Copy the code

Complexity analysis

  • Time complexity O(n*k) Each element is moved 1 step (O(n)) k times (O(k)).
  • Space complexity O(1) No additional space is used.

Method two: Use extra arrays

algorithm

We can use an extra array to put each element in the right place, the original array with the subscript I and we can put it at the length of the array I plus k %. Then copy the new array into the original array.

This solution uses a trick a[(I +k) % nums.length] = nums[I]; And that’s the key to this problem.

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  let a = []; // 
  for(let i = 0; i < nums.length; i++) {
    a[(i+k) % nums.length] = nums[i];
  }
  for(let i = 0; i < nums.length; i++) { nums[i] = a[i]; }}Copy the code

Complexity analysis

  • The time complexity O(n) requires a traversal to place the number in the new array, and another traversal to copy the new array into the original array
  • Space complexity O(n) Another array needs the length of the original array to hold the data