二维数组对角线填充

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

- halu

---

请问如何以对角线方式遍历矩阵？答案在这里：https://dev59.com/LnI-5IYBdhLWcg3wlpeW - nem035

@nem 稍微有些不对。但基本上很接近了。这其实是一个比想象中更难以可视化的算法。 - Compass

类似于这个问题 https://dev59.com/qVbUa4cB1Zd3GeqPA7L2 不完全相同，但是原理相似。 - James Montagne

这实际上是SO的缺点。应该标记为“重复”的问题得到了评分。几乎相同的问题已经在这里存在：https://dev59.com/LnI-5IYBdhLWcg3wlpeW - Arslan Ali

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符号表示法中的一个最优O(n^2)的类算法; 然而，它实际上执行了2*n^2次迭代，而最佳解决方案将只执行n^2次。

- Luke Willis

---

这里我有一个问题，这个算法是什么，或者请给一个提示，如何先添加行，然后再添加列？ - halu

@halu 完成了我的实现。应该适用于你。 - Luke Willis

我刚刚写了一个O(n^2)的代码。它有一些动态规划的方面。虽然有点凌乱，可能有更好的写法，但它适用于任何维度。 - Jay

吹毛求疵：O(2n^2) 是 O(n^2)。在大O符号中，常数是不相关的。 - You

是的，@你说得对。但出于完全透明的精神，我想要做出区分。 - Luke Willis

Answer 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个计算单元的机器，它们可以一次性计算整个矩阵。

- Kay

---

我喜欢你的解决方案。它确实是O(n^2)（请注意嵌套循环意味着您将执行n * n次操作）。这与我发布解决方案后想到的相同。 - Luke Willis

Answer 3

对角线长度为M乘以N的矩阵，带有稳健的数组格式

考虑到许多答案已经涵盖了基本的N乘以N数组，并且一些方法非常高效，因此我制作了一个更加稳健的版本，可处理M乘以N数组，并配备了一个漂亮的格式化打印机，供您享用/ masochistic查看。

该方法的效率为O（N ^ 2）。 打印机的格式为O（N ^ 2）。

代码

主要内容

您可以设置任何行和列，假设其为正整数值。

public static void main(String[] args) {
    //create an M x N array
    int rows = 20;  
    int columns = 11;
    int[][] testData = new int[rows][columns];

    //iteratively add numbers
    int counter = 0;
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < columns; j++)  {
            testData[i][j] = ++counter;
        }
    }

    //print our test array
    printArray(testData);
    System.out.println("");
    //print our diagonal array
    printArray(diagonal(testData));
}

打印二维数组

该方法特别适用于此示例，通过使用M x N确定条目数量，然后计算数字数。如果您想要显示基于数组中最长项的任何大小的数组，则可以轻松地调整此代码以执行该操作。这是一个不错的挑战，最好由读者分配。 O（N ^ 2）为此，但由于必须搜索具有最大值的数组，因此需要具有最大数字的搜索将自然需要另外O（N ^ 2）。

static void printArray(int[][] array) {
    //get number of digits
    int count = array.length * array[0].length;
    //get power of function
    int power;

    //probably the only time I'd ever end a for loop in a semicolon
    //this gives us the number of digits we need
    //You could also use logs I guess but I'm not a math guy
    for(power = 0; count / Math.pow(10, power) > 1; power++);

    for(int i = 0; i < array.length; i++){
        System.out.print("{");
        for(int j = 0; j < array[0].length; j++){
           //Let's say Power is 0. That means we have a single-digit number, so we need
           // +1 for the single digit. I throw in 2 to make it extra wide
           System.out.print(String.format("%" + Integer.toString(power + 2) 
                   + "s", Integer.toString(array[i][j])));
        }
        System.out.println("}");
     }
}

对角线转换器

当我们考虑M x N时，有很多边缘情况需要测试，因此我已经进行了测试并似乎已经覆盖了所有情况。虽然不是最整洁的，但似乎能正常工作。

static int[][] diagonal(int[][] input) {
    //our array info 
    final int numRows = input.length;
    final int numColumns = input[0].length;
    int[][] result = new int[numRows][numColumns];

    //this is our mobile index which we will update as we go through 
    //as a result of certain situations
    int rowIndex = 0;
    int columnIndex = 0;
    //the cell we're currently filling in
    int currentRow = 0;
    int currentColumn = 0;
    for(int i = 0; i < numRows; i++) {
        for(int j = 0; j < numColumns; j++) {
            result[currentRow][currentColumn] = input[i][j];
            //if our current row is at the bottom of the grid, we should
            //check whether we should roll to top or come along
            //the right border
            if(currentRow == numRows - 1) {
                //if we have a wider graph, we want to reset row and
                //advance the column to cascade
                if(numRows < numColumns && columnIndex < numColumns - 1 ) {
                    //move current row down a line
                    currentRow = 0;
                    //reset columns to far right
                    currentColumn = ++columnIndex;
                }
                //if it's a square graph, we can use rowIndex;
                else {
                    //move current row down a line
                    currentRow = ++rowIndex;
                    //reset columns to far right
                    currentColumn = numColumns - 1;
                }
            }
            //check if we've reached left side, happens before the 
            //top right corner is reached
            else if(currentColumn == 0) {
                //we can advance our column index to the right
                if(columnIndex < numColumns - 1) {
                    currentRow = rowIndex;                        
                    currentColumn = ++columnIndex;
                }
                //we're already far right so move down a row
                else {
                    currentColumn = columnIndex;
                    currentRow = ++rowIndex;
                }
            }
            //otherwise we go down and to the left diagonally
            else {
                currentRow++;
                currentColumn--;
            }

        }
    }
    return result;
}

样例输出

Input
{   1   2   3}
{   4   5   6}
{   7   8   9}
{  10  11  12}

Output
{   1   2   4}
{   3   5   7}
{   6   8  10}
{   9  11  12}


Input
{   1   2   3   4   5   6}
{   7   8   9  10  11  12}
{  13  14  15  16  17  18}
{  19  20  21  22  23  24}
{  25  26  27  28  29  30}
{  31  32  33  34  35  36}

Output
{   1   2   4   7  11  16}
{   3   5   8  12  17  22}
{   6   9  13  18  23  27}
{  10  14  19  24  28  31}
{  15  20  25  29  32  34}
{  21  26  30  33  35  36}

Input
{    1    2    3    4    5    6}
{    7    8    9   10   11   12}
{   13   14   15   16   17   18}
{   19   20   21   22   23   24}
{   25   26   27   28   29   30}
{   31   32   33   34   35   36}
{   37   38   39   40   41   42}
{   43   44   45   46   47   48}
{   49   50   51   52   53   54}
{   55   56   57   58   59   60}
{   61   62   63   64   65   66}
{   67   68   69   70   71   72}
{   73   74   75   76   77   78}
{   79   80   81   82   83   84}
{   85   86   87   88   89   90}
{   91   92   93   94   95   96}
{   97   98   99  100  101  102}
{  103  104  105  106  107  108}
{  109  110  111  112  113  114}
{  115  116  117  118  119  120}
{  121  122  123  124  125  126}
{  127  128  129  130  131  132}
{  133  134  135  136  137  138}
{  139  140  141  142  143  144}
{  145  146  147  148  149  150}

Output
{    1    2    4    7   11   16}
{    3    5    8   12   17   22}
{    6    9   13   18   23   28}
{   10   14   19   24   29   34}
{   15   20   25   30   35   40}
{   21   26   31   36   41   46}
{   27   32   37   42   47   52}
{   33   38   43   48   53   58}
{   39   44   49   54   59   64}
{   45   50   55   60   65   70}
{   51   56   61   66   71   76}
{   57   62   67   72   77   82}
{   63   68   73   78   83   88}
{   69   74   79   84   89   94}
{   75   80   85   90   95  100}
{   81   86   91   96  101  106}
{   87   92   97  102  107  112}
{   93   98  103  108  113  118}
{   99  104  109  114  119  124}
{  105  110  115  120  125  130}
{  111  116  121  126  131  136}
{  117  122  127  132  137  141}
{  123  128  133  138  142  145}
{  129  134  139  143  146  148}
{  135  140  144  147  149  150}

- Compass

Answer 4

你需要将从索引0到n的x/y（从0到x*y）进行转换，并从索引回到x/y...

public void toPos(int index){
    return...
}

public int toIndex(int x, int y){
    return...
}

我已经把具体实现细节交给你了。

- Martin Frank

Answer 5

Luke的直觉是正确的 - 你正在处理下向左倾斜的对角线。另一件需要注意的事情是对角线的长度：1、2、3、2、1。我还假设矩阵是正方形的。如果调整for循环指数，可以得到以下结果：

    int len = 1;
    int i = 1;
    while(len <= arr.length){
        //Fill this diagonal of length len
        for(int r = 0; r < len; r++){ 
            int c = (len - 1) - r;
            arr[r][c] = i;
            i++;
        }

        len++;
    }
    len--; len--;
    while(len > 0){
        //Fill this diagonal of length len
        for(int c = arr.length - 1; c > (arr.length - len - 1); c--){ 
            int r = arr.length - len + 2 - c;
            arr[r][c] = i;
            i++;
        }

        len--;
    }

    System.out.println(Arrays.deepToString(arr));

- Mshnik

---

当我只是复制代码时，它进行错误的计算！ - halu

Answer 6

这是从这里翻译成Java并根据您的问题进行了调整的代码。

int[][] convertToDiagonal(int[][] input) {
    int[][] output = new int[input.length][input.length];
    int i = 0, j = 0; // i counts rows, j counts columns

    int n = input.length;
    for (int slice = 0; slice < 2 * n - 1; slice++) {
        int z = slice < n ? 0 : slice - n + 1;
        for (int k = z; k <= slice - z; ++k) {
            // store slice value in current row
            output[i][j++] = input[k][slice - k];
        }
        // if we reached end of row, reset column counter, update row counter
        if(j == n) {
            j = 0;
            i++;
        }
    }
    return output;     
}

输入:

| 1 2 3 |
| 4 5 6 |
| 7 8 9 |

输出：

| 1 2 4 |
| 3 5 7 |
| 6 8 9 |

点击此处以运行测试代码

- nem035

Answer 7

这是一个简单的动态规划（ish）解决方案。基本上，您从上一步行动中学习。

注意：这是一个O(N^2)算法。

初始化：

 int m = 4;
 int n = 4;
 int[][] array = new int[m][n];;
 for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
        array[i][j] = 0;
    }
 }

工作内容：

array[0][0] = 1;
for(int i = 0; i < m; i++){
    if(i != 0){ array[i][0] = array[i-1][1]+1;} 
  // This is for the start of each row get 1+ the diagonal 
    for(int j = 1; j < n; j++){
        if(i == 0){
            array[i][j] = array[i][j-1]+j;
            // only for the first row, take the last element and add + row Count
        }else{
            if(i == m-1 && j == n -1){
               // This is only a check for the last element
                array[i][j] = array[i][j-1]+1;
                break;  
            } 
            // all middle elements: basically look for the diagonal up right.
            // if the diagonal up right is out of bounds then take +2 the 
            // prev element in that row
            array[i][j] = ((j+1) != (m)) ? array[i-1][j+1] +1: array[i][j-1]+2;
        }
    }
}

打印解决方案：

 for(int i = 0; i < m; i++){
     for(int j = 0; j < n; j++){
        System.out.print(array[i][j]);
     }
     System.out.println("");
  }
 return 0;
}

- Jay

---

问题是关于Java的。 - Luke Willis

Answer 8

这是您问题的完整可工作代码。如果您喜欢，可以复制粘贴。

public class FillArray{
    public static void main (String[] args){


    int[][] array = {
            {1,2,3},
            {4,5,6},
            {7,8,9}}; //This is your original array

    int temp = 0; //declare a temp variable that will hold a swapped value

    for (int i = 0; i < array[0].length; i++){
        for (int j = 0; j < array[i].length; j++){
            if (i < array.length - 1 && j == array[i].length - 1){ //Make sure swapping only
                temp = array[i][j];                                //occurs within the boundary  
                array[i][j] = array[i+1][0];                       //of the array. In this case
                array[i+1][0] = temp;                              //we will only swap if we are
            }                                                      //at the last element in each
        }                                                          //row (j==array[i].length-1)
    }                                                              //3 elements, but index starts
                                                                   //at 0, so last index is 2 
  }                                                                   
  }

- m8L