对角线遍历数组

2022-09-04 20:09:17

我有一大个任意大小的数组。它是一个方形数组。我试图掌握如何像a而不是a一样对角线遍历它(我已经知道如何做)。到目前为止,我有以下代码:/\

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 问题与整数数组存在类似的问题,其解基于数组元素的总和。但是我正在使用字符,所以我想不出一种方法来获得它。


答案 1

考虑单元格的坐标:

. 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 - 12 * (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();
}

但是,这最终会迭代许多越界坐标,因为它总是迭代所有可能的坐标,即使只有一个对角线包含所有可能的坐标。让我们更改循环,使其仅访问当前所需的坐标。yyyyk

越界坐标的一个条件是 。替换定义并解决:x < 0x

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

所以当 ,将是负数。因此,我们只想循环而 。y > kxy <= k

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

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

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

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();
}

注意:我只证明了这个代码是正确的。我还没有测试过。


答案 2

更简单的方法是检查索引是否等于数组的总和.length = 1;对于对角线右和对角线左撇子,只需检查 i 是否等于 j

例:

digonalLeft sums \ of matrix,因为 (0,0) (1,1) (2,2) 使对角线变为对角线。对角线右和矩阵的 /,因为 (0+2) = (1+1) = (2+0) = 2 和 2 是数组。length - 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];
    }    
}