用JavaScript旋转数组的两种方法

作者 : IT 大叔 本文共1704个字,预计阅读时间需要5分钟 发布时间: 2020-10-15

有时,在技术面试中我们可能会遇到的最棘手的问题是乍一看似乎很简单的问题。

由于我们使事情变得过于复杂,或者根本不了解使用这些数据类型的一些更基本的构建基块,因此编写看似简单的数组或字符串算法通常会使我们绊倒。

一个完美体现这一点的问题是旋转数组


提示

假设您获得了一个数字数组(nums),以及一个整数,该数字应将该数组右边“旋转”(k)多少次。

这是什么意思?让我们对其进行可视化:

nums = [1, 2, 3, 4, 5]

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

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

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

如您所见,“旋转”数组只是将这些值向右(或向左)移动,然后将它们放回数组的另一端,就像旋转圆盘传送带一样。

现在,如何去做呢?


解决方案

使这个问题成为采访环境中一个引人注目的问题的原因在于,有多种解决方法,所有这些方法对运行时和空间复杂性的影响不同。看到候选人解决​​和解释“简单”问题的方式不同是一个很好的问题,因为每个人的做法可能都不一样。

今天,我们将研究两个潜在的解决方案:

  1. 使用.pop()和.unshift()数组方法的“强力”方法。
  2. 使用数组反转的更复杂的解决方案。

首先,我们看一下代码,然后分解其中发生的事情。

1.蛮力

const rotateArray1 = function(nums, k) {

  for (let i = 0; i < k; i++) {
      nums.unshift(nums.pop());
  }

  return nums;
}

这被认为是“强力”方法,因为它本质上是我们一开始可能考虑问题的最直接的方法。

我们知道我们想从数组的末尾取出某些东西,然后放到前面,我们知道我们要这样做(k)次,对吗?

该解决方案将确切的方向放入代码中。我们在每次循环pop()上运行一次for循环(k)次,将数组的最后一个元素作为参数,并将其作为unshift()的参数提供给数组的前面。然后,我们在最后返回数组。

这里的运行时复杂度为O(n * k),因为每次我们使用unshift()时,JavaScript都会在底层隐藏数组中的每个元素。

因为我们要就地修改原始数组,所以空间复杂度是O(1)或恒定空间。大!

2.冲销

const rotateArray2 = function(nums, k) {

  // reverse helper function
  function reverse(arr, start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }

  k %= nums.length;

  reverse(nums, 0, (nums.length - 1));
  reverse(nums, 0, (k - 1));
  reverse(nums, k, (nums.length - 1));

  return nums;
}

到目前为止,这是三个中最有趣的解决方案。这是您最初可能不会想到的算法解决方案,但是可能在考虑了“更大的画面”一段时间后才想到。

如果可视化旋转的数组,则会注意到一种模式:

nums = [1, 2, 3, 4, 5]

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

// original array reversed
[5, 4, 3, 2, 1]

// reverse just the first (k) elements
[4, 5, 3, 2, 1]

// see where we're going?

// reverse from (k) to the end
[4, 5, 1, 2, 3]

这样就得到了轮换结果!

同样,这是您最初可能不会想到的逻辑飞跃,但是在我们已针对此问题设置的范围内完美地工作了。

对于我们的实际解决方案,我们正在做的是建立一个辅助函数,该函数接收一个数组,一个起始索引和一个终止索引,然后使用ES6语法在递增之前交换array [start]和array [end]元素并递减指针。

根据上面的示例,我们知道我们需要调用此函数三次:

  1. 一次反转整个阵列。
  2. 一次从nums [0]反转为k。
  3. 一旦从k反转到结尾。

我们完成了!

这里的运行时复杂度为O(n * 3),因为我们仍然需要至少反转一次每个元素,并且我们将这样做三遍。

这里的空间复杂度再次为常数O(1)。还是很棒!

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 用JavaScript旋转数组的两种方法

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论