对角遍历2D数组(矩阵) [英] Traverse 2D Array (Matrix) Diagonally

问题描述

所以我发现此线程对于遍历数组非常有帮助对角地.我仍然坚持镜像.例如:

So I found this thread that was extremely helpful in traversing an array diagonally. I'm stuck though on mirroring it. For example:

var m = 3;
var n = 4;
var a = new Array();
var b = 0;

for(var i = 0; i < m; i++) {
  a[i] = new Array(n);
  for(var j = 0; j < n; j++) {
    a[i][j] = b;
      b++;
  }
}

for (var i = 0; i < m + n - 1; i++) {
  var z1 = (i < n) ? 0 : i - n + 1;
  var z2 = (i < m) ? 0 : i - m + 1;
  for (var j = i - z2; j >= z1; j--) {
    console.log(a[j][i - j]);
  }
}

控制台读取[[0],[4,1],[8,5,2],[9,6,3],[10,7],[11]]

我希望它读[[8],[4,9],[0,5,10],[1,6,11],[2,7],[3]]

被绊倒了一段时间，就像魔方> _<

Been stumped for awhile, it's like a rubik's cube >_<

推荐答案

好吧，我发现整个z1，z2逻辑有点难以理解，所以我做了一些不同的事情:

Well, I found the whole z1, z2 logic a bit unreadable, so I did it a bit differently:

var m = 3;
var n = 4;
var a = new Array();
var b = 0;

for(var i = 0; i < m; i++) {
  a[i] = new Array(n);
  for(var j = 0; j < n; j++) {
    a[i][j] = b;
      b++;
  }
}

var out = new Array();
for (var i = 1 - m; i < n; i++) {
    var group = new Array();
    for (var j = 0; j < m; j++) {
        if ((i + j) >= 0 && (i + j) < n) {
            group.push(a[j][i + j]);
        }
    }
    out.push(group);
}
console.log(out);

将[[8], [4, 9], [0, 5, 10], [1, 6, 11], [2, 7], [3]]打印到控制台.

您的矩阵构造为您提供了一个这样的矩形(其中a数组是行的集合):

Your matrix construction gives you a rectangle like this (where your a array is the set of rows):

 0  1  2  3
 4  5  6  7
 8  9 10 11

这意味着对角线在此网格上方:

Which means the diagonals are over this grid:

 #  #  0  1  2  3
    #  4  5  6  7  #
       8  9 10 11  #  #

现在，我们只是在一个偏斜的矩形上循环，这看起来像是规范化的:

Now we're just looping over a skewed rectangle, that would look like this normalised:

 #  #  0  1  2  3
 #  4  5  6  7  #
 8  9 10 11  #  #

现在，您会发现，对于所添加的每一行，您都会得到一个额外的列(以#开头)，并且第一列现在已偏移了该数量(如果您想保留其中的第一行)将下面的行滑动到左侧).因此，对于我们的外部for循环(在列上)，第一列实际上是旧的第一列0，减去行数m加上1，得出0 - m + 1或.最后一列有效地保留在原位，因此我们仍在循环至n.然后，只需考虑每列&循环遍历每个m行(内部for循环).

Now you'll notice that for each row you add, you end up with an extra column (starting with a #) and that the first column is now skewed by this amount (if you imagine holding the first row in place & sliding the rows below to the left). So for our outer for loop (over the columns), the first column is effectively the old first column, 0, minus the number of rows m, plus 1, which gives 0 - m + 1 or 1 - m. The last column effectively stays in place, so we're still looping to n. Then its just a matter of taking each column & looping over each of the m rows (inner for loop).

当然，这会给您留下一堆undefined(在上面的网格中的#)，但是我们可以通过简单的if跳过它们，以确保我们的i& j在m& n范围.

Of course this leaves you with a bunch of undefineds (the #s in the grid above), but we can skip over them with a simple if to make sure our i & j are within the m & n bounds.

效率可能略低于z1/z1版本，因为我们现在遍历冗余的#单元，而不是对其进行预先计算，但是它不应该在现实世界中产生任何差异.我认为代码最终更具可读性.

Probably slightly less efficient than the z1/z1 version since we're now looping over the redundant # cells rather than pre-calculating them, but it shouldn't make any real world difference & I think the code ends up much more readable.

这篇关于对角遍历2D数组(矩阵)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！