沿对角线遍历数组

Question

沿对角线遍历数组

13

我有一个任意大小的大数组，它是一个方形数组。我想知道如何像“/”一样沿着对角线遍历它，而不是像“\”那样（我已经知道如何做了）。我到目前为止有以下代码：

char[][] array = new char[500][500];
//array full of random letters
String arrayLine = "";
for (int y = 0; y < array.length; y++) {
    for (int x = 0; x < array.length; x++) {
        for (???) {
            arrayLine = arrayLine + array[???][???];
        }
    }
    System.out.println(arrayLine);
}

我有三个循环，因为这是我用来实现另一个对角线的方法：

for (int y = 0; y < array.length; y++) {
    for (int x = 0; x < array.length; x++) {
        for (int z = 0; z < array.length-y-x; z++) {
            arrayLine = arrayLine + array[y+z][x+z];
        }
    }
    System.out.println(arrayLine);
}

在我的尝试中，我一直超出了边界，并收到了一个ElementOutOfBounds异常。假设数组如下所示（3x3而不是500x500）：

A B C
D E F
G H I

我想将以下内容作为字符串打印出来：

A
BD
CEG
FH
I

之前的一个SO问题涉及整数数组的类似问题，并且解决方案基于数组元素的总和。但是我正在使用字符，所以我想不出一种方法来解决。

- gator

3

考虑将数组中每个点的i和j相加时会发生什么。您会注意到B（(0,1)）和D（(1,0)）的总和都为1。在解决问题时，请考虑这个应用程序。注意：检查边界也很重要。 - Obicere

我不太确定我理解了。 A = 0,0，B + D = 1,1，C + E + G = 3,3，然后是3,3，然后是2,2... - gator

2

通过“i和j”，我指的是坐标。C，E和G的值为2。F和H的值为3。I的值为4。 - Obicere

我更新了我的问题以更好地反映我想要的内容。您的建议很有道理，但我想我的过度简化阻碍了我。 - gator

2个回答

1

更简单的方法是检查索引的总和是否等于数组长度= 1; 对于diagonalRight和diagonalLeft，只需检查i是否等于j��可。

示例：

digonalLeft求矩阵的和，因为（0,0）（1,1）（2,2）组成对角线。 diagonalRight求矩阵的/总和，因为（0 + 2）=（1 + 1）=（2 + 0）= 2，而2是数组长度-1。

long diagonalLeft = 0;
long diagonalRight = 0;

for (int i = 0; i < array.lenth - 1; i++) {
    for (int j = 0; j < array.length -1; j++) {
        if (i == j) digonalLeft += array[i][j];
        if (i + j == array.length - 1) diagonalRight += array[i][j];
    }    
}

- user1863196

对于循环，应该使用 <= 而不是 <，因为您正在从数组长度中减去 -1。 - Gilles

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rob mayoff · Accepted Answer

想一想单元格的坐标：

. 0 1 2
0 A B C
1 D E F
2 G H I

对于任意一条对角线，所有元素都有一个共同点：它们的坐标之和是一个恒定值。以下是这些恒定值：

0 = 0+0 (A)
1 = 1+0 (B) = 0+1 (D)
2 = 2+0 (C) = 1+1 (E) = 0+2 (G)
3 = 2+1 (F) = 1+2 (H)
4 = 2+2 (I)

最小常量是最小的坐标和，为0。最大常量是最大的坐标和。由于每个坐标分量可以达到array.length - 1，因此最大常量是2 * (array.length - 1)。

因此，要做的就是遍历所有常量。对于每个常量，遍历其坐标总和等于该常量的元素。这可能是最简单的方法：

for (int k = 0; k <= 2 * (array.length - 1); ++k) {
    for (int y = 0; y < array.length; ++y) {
        int x = k - y;
        if (x < 0 || x >= array.length) {
            // Coordinates are out of bounds; skip.
        } else {
            System.out.print(array[y][x]);
        }
    }
    System.out.println();
}

然而，这将最终迭代许多越界坐标，因为它总是迭代所有可能的y坐标，尽管只有一个对角线包含所有可能的y坐标。让我们改变y循环，使其仅访问当前k所需的y坐标。

越界坐标的一个条件是x < 0。代入x的定义并解决：

x < 0
k - y < 0
k < y
y > k

因此，当 y > k 时，x 将为负数。因此我们只想在 y <= k 的情况下循环。

越界坐标的另一个条件是 x >= array.length。解决：

x >= array.length
k - y >= array.length
k - array.length >= y
y <= k - array.length

因此，当y <= k - array.length时，x将会太大。因此我们希望从0或k - array.length + 1开始y，以较大者为准。

for (int k = 0; k <= 2 * (array.length - 1); ++k) {
    int yMin = Math.max(0, k - array.length + 1);
    int yMax = Math.min(array.length - 1, k);
    for (int y = yMin; y <= yMax; ++y) {
        int x = k - y;
        System.out.print(array[y][x]);
    }
    System.out.println();
}

注意：我只证明了这段代码的正确性，但并未测试过它。