JavaScript中数组的螺旋遍历

Question

我正在解决一个编码问题，并编写一个函数来以蜗牛形式遍历嵌套数组（例如此处的示例）。例如，给定[[1,2,3], [8,9,4], [7,6,5]]的输入，该函数应输出[1,2,3,4,5,6,7,8,9]。在我的主要函数中，我创建了4个函数以在所有方向上遍历数组。在每个步骤中，我将当前网格位置的值推入并检查标志数组，以确定下一个位置是否已被访问。 我有两个问题： 1. 我无法成功克隆作为参数传递的数组。即使我使用array.slice(0)，新的flagsArray似乎是array的指针，当我修改flagsArray时，更改会反映在array中。为什么？ 2. 当我运行此测试时，我的克隆方法似乎有效：

var array = [0, 1];
var array_clone = array.slice(0);
array_clone[2] = 3;
console.log(array); // No changes to array

2. 执行traverseDown()时，我遇到了“flagsArray[(i+1)]未定义”的错误。这似乎是在尝试读取超出flagsArray索引的位置。但是如果我在一个while循环中检查flagsArray[i+1][j] === false && i < flagsArray.length，那么循环不应该在尝试读取数组之外的内容后停止吗？其中一个原因是因为flagsArray[flags.Array.length]将为未定义，因此不等于false，另一个原因是我还检查了i是否在flagsArray范围内。

以下是我的函数：

snail = function(array) {
  console.log(array);
  var output = [];

  var flagsArray = array.slice(0);

  // Populating flagsArray with false values
  // False = index not visited yet
  for (var i = 0; i < flagsArray.length; i++) {
    for (var j = 0; j < flagsArray[i].length; j++) {
      flagsArray[i][j] = false;
    }
  }
  var i = 0;
  var j = 0;

    var traverseRight = function() {
    while (flagsArray[i][j + 1] === false && j < flagsArray[i].length) {
      console.log(flagsArray[i][j].length + 'Traversing right Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      j++;
    } 
  }

  var traverseDown = function() {
    while (flagsArray[i + 1][j] === false && i < flagsArray.length) {
      console.log('Traversing Down Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      i++;
    }
  }

  var traverseLeft = function() {
    while (array[i][j - 1] === false && j >= 0) {
      console.log('Traversing left Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      j--;
    }
  }

  var traverseUp = function() {
    while (array[i][j] === false && j >= 0) {
      console.log('Traversing Up Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      i--;
    }
  }

  while (flagsArray[i][j + 1] === false) {
    traverseRight();
    traverseDown();
    traverseLeft();
    traverseUp();
  } 
  return output;
}

console.log(snail([[1,2,3],[8,9,4],[7,6,5]]));

- Patrick

Answer 1

问题 1

我无法成功克隆作为参数传递的数组。即使我使用 array.slice(0)，新的 flagsArray 似乎仍然是指向 array 的指针，当我修改 flagsArray 时，更改也会反映在 array 中。这是为什么？

这是因为您有一个二维数组，而您只复制了外部数组。它的每个元素都是原始的内部数组。

要对 array 进行深层复制，以便我们可以操纵它而不会改变原始值，我们必须复制每个内部数组：

var flags = new Array(array.length);
for (var i = 0; i < array.length; ++i) {
  flags[i] = array[i].slice();
}

（注：我已经更名flagsArray为flags。还请注意，slice()可以在没有参数的情况下调用以从索引0开始复制数组。）

我们可以使用Array.map更简洁地完成同样的操作：

var flags = array.map(function (subarray) {
  return subarray.slice();
});

但是如果我们立即用 false 覆盖数组值，复制数组值就没有意义：

for (var i = 0; i < flags.length; i++) {
  for (var j = 0; j < flags[i].length; j++) {
    flags[i][j] = false;
  }
}

如果我们在制作flag数组时将false值放入其中，就可以删除那个双重循环:

var flags = array.map(function (subarray) {
  return subarray.map(function () {
    return false;
  });
});

问题2

在执行traverseDown()时，我遇到了“flagsArray[(i + 1)]未定义”的错误。这看起来像是试图读取超出flagsArray索引的错误。但是如果我在while循环中检查flagsArray[i + 1][j] === false && i < flagsArray.length，那么一旦尝试读取数组之外的内容，循环不应该停止吗？

不，JavaScript不会防止越界访问数组。在这行代码中发生的情况是：

while (flagsArray[i + 1][j] === false && i < flagsArray.length) {

那是因为flagsArray[i + 1] 求值为 undefined，因为 i+1 超出了数组的最后一个元素。然后你试图查找[j], 程序崩溃，因为 undefined 没有任何属性。

你甚至没有评估 i < flagsArray.length。此外，这个测试也无法阻止非法索引，因为如果i 是最后一个元素的索引，那么 flagsArray[i + 1] 超出了边界。

总体观察

这个测试有两个问题：

while (flagsArray[i][j + 1] === false && j < flagsArray[i].length) {

首先，在访问数组之前，您忽略了检查数组索引。其次，您没有测试正确的值。您应该在访问flagsArray[i][j + 1]之前测试j + 1：

while (j + 1 < flagsArray[i].length && flagsArray[i][j + 1] === false) {

还有其他三个测试存在类似的问题。

作为写四个函数的替代方案，建议您编写遍历逻辑一次，并使其依赖于一个名为orientation的变量，该变量的值从0到3不等。唯一随着运动方向而不同的是增加网格索引的数量。您可以在带有orientation作为数组索引的一对数组中查找这些递增值。

递增数组如下所示：

var dr = [ -1, 0, 1, 0 ],  // North, east, south, west.
    dc = [ 0, 1, 0, -1 ];

给定网格位置r，c，可以按以下方式计算下一个位置：

var R = r + dr[orientation],
    C = c + dc[orientation];

以下代码片段展示了这种方法。

function print(line) {
  document.getElementById('message').innerHTML += line + '<br><br>';
}

var snail = function(array) {
  var result = [];

  var flags = array.map(function (subarray) {
    return subarray.map(function () {
      return false;
    });
  });
  print(JSON.stringify(array));

  var numRows = flags.length,
      numCols = flags[0].length,
      numElements = numRows * numCols,
      dr = [ -1, 0, 1, 0 ],  // North, east, south, west.
      dc = [ 0, 1, 0, -1 ],
      r = 0,
      c = 0,
      orientation = 1;       // Start heading east.

  var count = 0;

  while (result.length < numElements) {
    result.push(array[r][c]);
    flags[r][c] = true;
    var R = r + dr[orientation],  // Calculate the next grid position.
        C = c + dc[orientation];
    if (R >= 0 && R < numRows && C >= 0 && C < numCols && !flags[R][C]) {
      r = R;                      // If the position is valid, go ahead.
      c = C;
    } else {
      orientation = (orientation + 1) % 4;
      r = r + dr[orientation];    // Otherwise, turn clockwise and recalculate.
      c = c + dc[orientation];
    }
  }

  return result;
}

window.onload = function () {
  print(snail([ [1, 2, 3],
                [8, 9, 4],
                [7, 6, 5] ]));
};

body {
  font-family: sans-serif;
}

<div id="message"></div>

- Michael Laszlo

Answer 2

螺旋数组（ES6）

试试这个：

function spiral(array) {
    const matrix = [...array];
    const arr = [];

    while (matrix.length) {
        arr.push(
            ...matrix.shift(),
            ...matrix.map(a => a.pop()),
            ...matrix.pop().reverse(),
            ...matrix.map(a => a.shift()).reverse()
        );
    }
    return arr;
}

- Lior Elrom