通过递归交换解决“数组旋转leetcode #189”

Question

我正在研究 LeetCode 问题 #189 旋转数组:

给定一个整数数组

nums

，将数组向右旋转

k

步， 其中

k

是非负数。

我尝试通过从元素

k

开始，然后替换序列上的下一个元素来解决这个问题。它适用于某些情况，但对于其他一些情况，并非所有元素都已达到，然后我需要为

k+1

运行相同的代码，依此类推。

代码：

var rotate = function(nums, k) {
    let len = nums.length

    // start with element at index K
    let curr_index = k
    let curr_element = nums[curr_index]

    let target_index = -1

    // stop when a full cycle is completed
    while (target_index !== k) {
        target_index = (curr_index + k) % len
        const target_element = nums[target_index]

        // replace target with current element
        nums[target_index] = curr_element

        // set current to be equal to target
        curr_element = target_element
        curr_index = target_index
    }
};

它适用于案例

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

，但不适用于案例

[1,2,3,4], k=2

有没有办法通过这种“蛮力”方式进行真正的旋转来解决这个问题？

Answer 1

旋转让人想起移位，JavaScript 数组有 4 个相关方法：shift、unshift、pop 和 push。

我们走吧：

var rotate = function(nums, k) {
  for (var i = 0; i < k; i++) {
    // this replaces in place
    // i.e: it changes nums array
    var x = nums.pop()
    nums.unshift(x)
  }
  return nums
}


var arr = [1, 2, 3, 4, 5]
var result = rotate(arr, 2)
console.log("" + arr)
console.log("" + result)