Java 对角线遍历数组

Traverse an array diagonally

提问by gator

I have a large array of arbitrary size. It's a square array. I'm trying to grasp how to traverse it diagonally like a /rather than a \(what I already know how to do). I have the following code thus far:

我有一个任意大小的大数组。这是一个方阵。我试图掌握如何像 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);
}

I have three loops, because this is how I did the other diagonal:

我有三个循环，因为这是我做另一个对角线的方式：

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

In my attempts, I keep going outside the boundaries and get an ElementOutOfBounds exception. Say the array is as below (a 3x3 instead of 500x500):

在我的尝试中，我不断超出边界并获得 ElementOutOfBounds 异常。假设数组如下（3x3 而不是 500x500）：

A B C
D E F
G H I

I want to print out the following as strings:

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

A
BD
CEG
FH
I

A previous SO question had a similar problem with integer arrays, and the solution is based off of the sum of array elements. But I'm working with chars, so I can't think of a methodology to get it.

以前的 SO 问题对整数数组有类似的问题，解决方案基于数组元素的总和。但是我正在使用字符，所以我想不出一种方法来获得它。

采纳答案by rob mayoff

Think about the coordinates of the cells:

考虑单元格的坐标：

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

For any diagonal, all of the elements have something in common: the sum of an element's coordinates is a constant. Here are the constants:

对于任何对角线，所有元素都有一个共同点：元素坐标之和是一个常数。以下是常量：

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)

The minimum constant is the smallest coordinate sum, 0. The maximum constant is the largest coordinate sum. Since each coordinate component can go up to array.length - 1, the maximum constant is 2 * (array.length - 1).

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

So the thing to do is iterate over the constants. For each constant, iterate over the elements whose coordinates sum to the constant. This is probably the simplest approach:

所以要做的是迭代常量。对于每个常量，迭代其坐标总和为常量的元素。这可能是最简单的方法：

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

However, that will end up iterating over a lot of out-of-bounds coordinates, because it always iterates over all possible ycoordinates, even though only one diagonal contains all possible ycoordinates. Let's change the yloop so it only visits the ycoordinates needed for the current k.

然而，这最终会迭代很多越界坐标，因为它总是迭代所有可能的y坐标，即使只有一条对角线包含所有可能的y坐标。让我们改变y循环，让它只访问y当前k.

One condition for out-of-bounds coordinates is x < 0. Substitute the definition of xand solve:

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

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

So when y > k, xwill be negative. Thus we only want to loop while y <= k.

所以当y > k，x将是负数。因此我们只想循环 while y <= k。

The other condition for out-of-bounds coordinates is x >= array.length. Solve:

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

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

So when y <= k - array.length, xwill be too large. Thus we want to start yat 0 or k - array.length + 1, whichever is larger.

所以当y <= k - array.length，x会太大。因此，我们希望从y0 或开始k - 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();
}

Note: I have only proven this code correct. I have not tested it.

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

回答by user1863196

Much simpler way is to check the sum if indexes are equals to the array.length = 1; for diagonalRight and for diagonalLeft just check if i is equals j

更简单的方法是检查总和，如果索引等于 array.length = 1; 对于 diagonalRight 和 diagonalLeft 只需检查 i 是否等于 j

Example:

例子：

digonalLeft sums \ of matrix, because (0,0) (1,1) (2,2) makes the diagonal. diagonalRight sums / of matrix, because (0+2) = (1+1) = (2+0) = 2 and 2 is the array.length - 1.

digonalLeft 对矩阵求和，因为 (0,0) (1,1) (2,2) 使对角线。diagonalRight 和 / 的矩阵，因为 (0+2) = (1+1) = (2+0) = 2 并且 2 是 array.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];
    }    
}