×

关于javascript的算法:如何让数组进行反转操作

作者:Terry2023.01.13来源:Web前端之家浏览:2016评论:0
关键词:js

关于javascript的算法:如何让数组进行反转操作。

leecode题目-旋转数组

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例:

输入: nums = [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]

分析题目

  • 数组元素有序轮转,即轮转位置k,意味着,每个元素向后移k位,且长度n-k~n-1位置的元素会被挪移至最前方;

  • k为非负整数,所以,不存在向左轮转;

解题思路

在不使用额外数组的前提下,我们可以有如下思考, 设数组长度为length,则

  • 需要轮转k位,即数组的最后k位会进行挪移至数组前方,即,当我们反转数组后,可以得知[0,k-1],[k,lenth-1]这两个数组,即为轮转之后的对应数组,但是,两个数组中的元素排序是反的;

  • 接下来,依次反转[0,k-1],[k,lenth-1],这两个数组,得到的数组就是答案了。

代码:

const reverseArray = (nums, start, end) => {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start += 1;
    end -= 1;
  }
  return nums;
};
var reverseFunction = function(nums, k) {
  let length  = nums.length;
  nums = reverseArray(nums, 0, length - 1);
  nums = reverseArray(nums, 0, k - 1);
  nums = reverseArray(nums, k, length - 1);
};
reverseFunction([1,2,3,4,5,6,7],3);

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

复杂度分析

  • 时间复杂度:时间复杂度:O(n),其中 nn 为数组的长度。每个元素被翻转两次,一共 n 个元素,因此总时间复杂度为 O(2n)=O(n)。

  • 空间复杂度:O(1)。只需要常数空间存放若干变量。

其他解法

思路:

  • 既然轮转k位,即[length-1-k,length-1]位置的元素变为[0,k-1]

  • [0,length-1-k]位置的元素变为[length-1-k,length-1]

  • 所以我们只需要将原数组拆分为[0,k-1],[length-1-k,length-1],然后将其按照[length-1-k,length-1]+[0,k-1]组装成一个数组即可

代码:

var reverseFunction2 = function(nums, k) {
  let length  = nums.length;
  let arrayLeft = nums.slice(0,length-k);
  let arrayRight = nums.slice(length-k);
  // return [...new Set([...arrayRight,...arrayLeft])];
  return arrayRight.concat(arrayLeft);
};
reverseFunction2([1,2,3,4,5,6,7],3);

大家会发现上述代码中,我注释了一行,因为,绝对诱人会想使用new Set方法去合并两个数组,那么,请注意,千万不能使用,因为,new Set方法,会讲两个数组进行合并后去重,如果原数组中出现相同元素,则,new Set将会给使用者狠狠上一课!

您的支持是我们创作的动力!
温馨提示:本文作者系Terry ,经Web前端之家编辑修改或补充,转载请注明出处和本文链接:
https://www.jiangweishan.com/article/js20230113a2.html

网友评论文明上网理性发言 已有0人参与

发表评论: