javascript - 更好/更快的算法来旋转数组？

Question

给定一个数组，将数组向右旋转 k 步，其中 k 为非负数。

示例 1：

输入： [1,2,3,4,5,6,7] 和 k = 3

输出： [5,6,7,1,2,3,4]

解释：

第 1 步：[7,1,2,3,4,5,6]

第 2 步：[6,7,1,2,3,4,5]

第 3 步：[5,6,7,1,2,3,4]

我的解决方案：

var rotate = function(nums, k) {
while(k>0){ 
 let lastelm = nums[nums.length-1];
  for(let i =nums.length; i>0;i--){
    temp = nums[i-1];
    nums[i-1] = nums[i-2];    
  }
  nums[0]=lastelm
  k--;
 }     
};

我认为我的解决方案是 O(k*nums.length)

我修改整个数组的次数与 k 一样多

有什么更好的方法呢？

标签： javascriptarraysalgorithmdata-structures

Answer 1

您可以使用.slice从数组中取出两个切片 - 一个从开头开始，在中间结束，另一个切片从中间开始并在末尾结束。然后以相反的顺序重新组合它们：

const rotate = (nums, k) => [...nums.slice(-k), ...nums.slice(0, -k)];
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

如果您必须改变现有数组，则：

const rotate = (nums, k) => {
  const moveAfter = new Array(k).concat(nums.slice(0, -k));
  Object.assign(nums, nums.slice(-k), moveAfter);
  return nums;
};
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

如果k可能大于数组的长度，请先对其使用取模：

const rotate = (nums, kPossiblyOutOfRange) => {
  const k = kPossiblyOutOfRange % nums.length;
  return [...nums.slice(-k), ...nums.slice(0, -k)];
}
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 8));
console.log(rotate([1,2,3,4,5,6,7], 3));