2d阵列对角填充

Question

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

Answer 1

好吧,如果你要枚举索引以便填充模式,你就会得到

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

因此,您需要遍历两个索引的总和.即,添加剂总量.如您所见,0,0总计0 1,0和0,1总计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);
}

请注意,虽然此实现适用于所有矩阵大小(和形状),但它不会尽可能高效.其中n是matrix.length(假设一个方阵),该实现是一个最优O(n^2)在大O符号类算法; 然而,它有效地执行2*n^2迭代,而最佳解决方案只会执行n^2.

Answer 2

你想要得到这样的东西:

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

在大小为NxN的网格中,对于网格中的每个点(x,y),您可以像这样确定值(仍然需要对偏移量进行一些修正,参见最终公式):

• 如果你在左上半部分,计算你上方和左边三角形的面积,并添加你从顶部的距离

• 如果你是在右下方(或中间),计算下面的三角形和右的你的区域,从底部添加你的距离和减去从整个区域

让我们试试它作为一个公式:

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单位的机器,他们可以在一次操作中计算整个矩阵.