2D阵列对角线填充

arrays java

2022-09-02 12:39:48

1 2 3
4 5 6
7 8 9

这是我的正常数组，但我需要像这样对角线

1 2 4
3 5 7
6 8 9

这是使它工作的非常愚蠢的方法，但即使它不起作用，因为我无法找到第二列元素。

for (i = 0; i < arr.length; ++i) {
    for (n = 0; n < arr[0].length; ++n) {
        if (i == 0 && n == 0){
            arr[i][n] = 0;
        } else if (i == 0 && n == 1) {
            arr[i][n] = 2;
        } else if (i == 1 && n == 0) {
            arr[i][n] = 3;
        } else if (n == 0) {
            arr[i][n] = arr[i - 1][n] - arr[i - 2][n] + 1 + arr[i - 1][n];
        } else {
            arr[i][n] = arr[i][n - 1] - arr[i][n - 2] + 1 + arr[i][n - 1];
        }
    }
}

答案 1

好吧，如果您要枚举索引以用于该填充模式，您将获得

0,0
1,0
0,1
2,0
1,1
0,2
2,1
1,2
2,2

因此，您需要循环访问两个索引的总和。即加法总量。如您所见，总计 0，总计 1，依此类推。给我们这样的东西：0,01,00,1

0 1 2
1 2 3
2 3 4

要迭代此对角线模式，我们可以执行以下操作：

// set up your matrix, any size and shape (MxN) is fine, but jagged arrays will break
int[][] matrix = {{0,0,0},{0,0,0},{0,0,0}};

// number is the value we will put in each position of the matrix
int number = 1;

// iterate while number is less than or equal to the total number of positions
// in the matrix. So, for a 3x3 matrix, 9. (this is why the code won't work for
// jagged arrays)
for (int i = 0; number <= matrix.length * matrix[0].length; i++) {
    // start each diagonal at the top row and from the right
    int row = 0;
    int col = i;

    do {
        // make sure row and length are within the bounds of the matrix
        if (row < matrix.length && col < matrix[row].length) {
            matrix[row][col] = number;
            number++;
        }

        // we decrement col while incrementing row in order to traverse down and left
        row++;
        col--;
    } while (row >= 0);
}

请注意，虽然此实现适用于所有矩阵大小（和形状），但它不会尽可能高效。其中 is （假设是一个平方矩阵），此实现是大 O 表示法的最优类算法;但是，它有效地执行迭代，而最优解只能执行。nmatrix.lengthO(n^2)2*n^2n^2

答案 2

你想实现这样的东西：

1 2 4 7
3 5 8 B
6 9 C E
A D F G

在大小为NxN的网格中，对于网格中的每个点（x，y），您可以像这样确定值（对于0处的偏移量仍需要一些更正，请参阅最终公式）：

如果您位于左上半部分，请计算您上方和左侧的三角形的面积，并添加您与顶部的距离
如果您位于右下半部分（或中间），请计算您下方和右侧三角形的面积，将距离底部的距离相加，然后从整个区域中减去该距离

让我们尝试将其作为公式：

int N = 4; int[][] v = new[N][N];
for(int y = 0; y < N; y++) for(int x = 0; x < N; x++)
v[x][y] = ( x + y < N ) ?
    ( ( x + y + 1 ) * ( x + y ) / 2 + y + 1 ) :
    ( N * N + 1 - ( N - y ) - ( 2 * N - x - y - 1 ) * ( 2 * N - x - y - 2 ) / 2 );

我不知道这有多复杂，但专家可以肯定地确认它是O（N^2）？另外，如果它有一些很酷的名字，如动态代码，请让我知道！

我在这里看到的优点是，你不需要在内存中跳来跳去，可以通过一次线性运行来填充所有字段。此外，将其作为与历史无关的公式可以由编译器优化或允许更好的并行化。如果你有一台具有N^2单位的机器，他们可以在一次操作中计算出整个矩阵。