javascript 更好/更快的阵列旋转算法?

cx6n0qe3  于 2023-01-24  发布在  Java
关注(0)|答案(4)|浏览(98)
    • 给定一个数组,将数组向右旋转k步,其中k为非负数。**
    • 示例1:**
    • 输入:**[1、2、3、4、5、6、7]且k = 3
    • 产出:**[5、6、7、1、2、3、4]
    • 说明:**

第一步:[7、1、2、3、4、5、6]
第二步:[6、7、1、2、3、4、5]
第三步:[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
还有什么更好的方法呢?

lmyy7pcs

lmyy7pcs1#

你可以使用.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可能大于数组的长度,则首先对其使用modulo:

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));
uxhixvfz

uxhixvfz2#

最简单的方法就是在读或写数组时跟踪移位,也就是说,存储一个常量“shift”,在读或写索引为i的数组时,调整为(i + shift)%(数组大小)。

cqoc49vn

cqoc49vn3#

unshiftpop的组合似乎有一个窍门:

var rotate = function(nums, k) {
    while (k > 0) { 
        nums.unshift(nums.pop());
        k--;
    }
}
sqougxex

sqougxex4#

var rotate = function(nums, k) {
  k = k % nums.length;
  revNums(nums, 0, nums.length - 1);
  revNums(nums, 0, k -1);
  revNums(nums, k , nums.length - 1);
};

var revNums = function(arr, start, end){
while(start < end){
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++;
    end--;
 }
}

相关问题