沿对角线遍历二维数组

Question

沿对角线遍历二维数组

23

我写了下面的代码来遍历一个数组的一半对角线：

String[][] b = [a,b,c]
               [d,e,f]
               [g,h,i];  

public void LoopDiag()
   for (int i = b.length - 1; i > 0; i--) {
       String temp = "";
       for (int j = 0, x = i; x <= b.length - 1; j++, x++) {
          temp = temp+b[x][j];
       }
       System.out.println(temp)
   }


   for (int i = 0; i <= b.length - 1; i++) {
        String temp = "";
        for (int j = 0, y = i; y <= b.length - 1; j++, y++) {
        temp = temp+b[j][y];
        }
        System.out.println(temp);
   }
}

现在它打印出对角线，即当前输出：

g dh aei bf c

我应该如何使其打印另一半的对角线，即所需输出：

a db gec hf i

- user243872

请将输出格式化，以便我们能够看到。 - Ruchira Gayan Ranaweera

1

你有尝试自己解决这个问题吗？你遇到了什么具体困难？这是你的作业吗？ - Andrey

12个回答

5

我写了以下代码。关键是要穷尽从顶部开始的所有对角线，然后转移到从侧面开始的对角线。我包括了一种将两个角度组合起来遍历西北-东南和东北-西南对角线的方法，以及分别遍历各自角度的独立方法。

public static void main(String[] args){
    int[][] m = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
    printDiagonals(m, DiagonalDirection.NEtoSW, new DiagonalVisitor() {     
        public void visit(int x, int y, int[][] m) {
            System.out.println(m[x][y]);
        }
    });
}

public enum DiagonalDirection{
    NWToSE,
    NEtoSW
}

private static abstract class DiagonalVisitor{
    public abstract void visit(int x, int y, int[][] m);
}

public static void printDiagonals(int[][] m, DiagonalDirection d, DiagonalVisitor visitor){

    int xStart = d==DiagonalDirection.NEtoSW ? 0 : m.length-1;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart>=0 && xStart<m.length){
            xLoop = xStart;
            yLoop = 0;
            xStart++;
        }else if(yStart<m[0].length){
            xLoop = d==DiagonalDirection.NEtoSW ? m.length-1 : 0;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;(xLoop<m.length && xLoop>=0)&&yLoop<m[0].length; xLoop=d==DiagonalDirection.NEtoSW ? xLoop-1 : xLoop+1, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }

    }

}

public static void printDiagonalsNEtoSW(int[][] m, DiagonalVisitor visitor){

    int xStart = 0;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart<m.length){
            xLoop = xStart;
            yLoop = 0;
            xStart++;
        }else if(yStart<m[0].length){
            xLoop = m.length-1;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;xLoop>=0 && yLoop<m[0].length; xLoop--, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }


    }
}

public static void printDiagonalsNWtoSE(int[][] m, DiagonalVisitor visitor){

    int xStart = m.length-1;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart>=0){
            xLoop = xStart;
            yLoop = 0;
            xStart--;
        }else if(yStart<m[0].length){
            xLoop = 0;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;xLoop<m.length && yLoop<m[0].length; xLoop++, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }       
    }
}

- AtlasMeh-ed

4

如果将问题细分为两个子问题，解决方案会变得更加简单：

Figure out the start of each diagonal.

Given the starting indices of a diagonal, print the diagonal.

public void printMatrixDiagonals(int[][] matrix) {

    int c = 0;
    int count = matrix.length + matrix[0].length -1;
    int i = 0, j = 0;
    //There can be at most  m + n -1 diagonals to be printed
    while (c < count) {
        //Start printing diagonals from i and j
        printDiagonal(i, j, matrix);
        if (i < matrix.length -1) {
            //We increment row index until we reach the max number of rows
            i++;
        } else if (j < matrix[0].length - 1) {
            //We are at maximum index of row; so its time to increment col index
            //We increment column index until we reach the max number of columns
            j++;
        }
        c++;
    }
}

打印对角线: 注意，每次我们开始打印每条对角线时，行的索引应该递减，列的索引应该递增。因此，给定每条对角线的起始索引，我们可以按以下方式打印对角线:

private void printDiagonal(int i, int j, int[][] m) {
    while (i >=0 && j< m[0].length ) {
        System.out.print(m[i][j] + " ");
        i--;
        j++;
    }
    System.out.println("");
}

- Big O

4

这适用于非正方形数组。它易于理解，但对每个对角线调用了一次min()和max()。

int ndiags = width +  height - 1;
System.out.println("---");
for (int diag = 0; diag < ndiags; diag++) {
    int row_stop = Math.max(0,  diag -  width + 1);
    int row_start = Math.min(diag, height - 1);
    for (int row = row_start; row >= row_stop; row--) {
        // on a given diagonal row + col = constant "diag"
        // diag labels the diagonal number
        int col = diag - row;
        System.out.println(col + "," + row);
        relax(col, row);
    }
    System.out.println("---");
}

以下是宽度为3，高度为3的输出结果：

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

宽度为3，高度为2

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

宽度为2，高度为3

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

- Greg Whittier

那太完美了！ - Stefan Reich

4

请自行查看需要循环遍历的索引：

#1 (0,0)               -> a
#2 (1,0)  (0,1)        -> bd
#3 (2,0)  (1,1)  (0,2) -> gec
#4 (2,1)  (1,2)        -> hf
#5 (2,2)               -> i

看每次迭代中指数的变化并创建你的算法。这并不难，所以要自己完成作业 ;)

- alex

你真的改变了我看问题的方式！把索引写下来使得解决方案变得非常容易。 - Vivek

2

这是一种非常直观的在 while 循环中打印对角矩阵的方法。

将问题整体泛化，而不是分为两部分，并在空间复杂度方面进行优化。

package algorithm;

public class printDiagonaly
{
    public static void main(String[] args)
    {
        int[][] a = new int[][]{{1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20}};

        int lr = 0;
        int lc = -1;
        int fr = -1;
        int fc = 0;
        int row = a.length - 1;
        int col = a[0].length - 1;

        while (lc < col || fc < col || fr < row || lr < row)
        {
            if (fr < row)
            {
                fr++;
            }
            else
            {
                fc++;
            }

            if (lc < col)
            {
                lc++;
            }
            else
            {
                lr++;
            }

            int tfr = fr;
            int tlr = lr;
            int tlc = lc;
            int tfc = fc;

            while (tfr >= tlr && tfc <= tlc)
            {

                System.out.print(a[tfr][tfc] + " ");
                tfr--;
                tfc++;
            }
            System.out.println("\n");
        }
    }
}

- brahmananda Kar

1

正如Alex在这里提到的，你需要在循环中查看索引。以下是我解决这个问题的方法。

Input:         
a b c    ----- (0,0) (0,1) (0,2)
d e f    ----- (1,0) (1,1) (1,2)
g h i    ----- (2,0) (2,1) (2,2)

Output:
a        ----- (0,0)
b d      ----- (0,1) (1,0)
c e g    ----- (0,2) (1,1) (2,0)
f h      ----- (1,2) (2,1)
i        ----- (2,2)

public class PrintDiagonal{

    public static void printDR(String[][] matrix, int rows, int cols){
        for(int c=0; c < cols; c++){
            for(int i=0, j=c; i< rows && j>=0;i++,j--){
                System.out.print(matrix[i][j] +" ");
             }
             System.out.println();
        }

        for(int r =1; r < rows; r++){
            for(int i =r, j= cols -1; i<rows && j>=0; i++,j--){
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args){
        String[][] matrix ={
            {"a","b","c"},
            {"d","e","f"},
            {"g","h","i"}
        };

        int rows = matrix.length;
        int columns = matrix[0].length; 
        printDR(matrix ,rows, columns);
    }
}

- leoflower

1

    String ar[][]={{"a","b","c"},{"d","e","f"},{"g","h","i"}};
    int size1=ar.length-1, size2=ar.length;

    for(int i=0; i<ar.length; i++)
    {   
        String a="";        
        for(int j=0, x=ar.length-1-i; j<ar.length-i; j++, x--)
        {
            if((j+x)==size1)
            a=a+ar[x][j];
        }
        size1--;

        System.out.println(a);
        a="";
        for(int j=i+1, x=ar.length-1; j<ar.length; j++, x--)
        {
            if((j+x)==size2)
            a=a+ar[x][j];
        }
        System.out.println(a);
        size2++;
    }

输出

gec hf db i a

- Apurv Jaiswal

你正确地分组了元素，但是将这些组返回到了错误的顺序中。请检查问题中这些组的正确位置。 - George Alexandria

1

这是代码：

public void loopDiag(String [][] b) {

        boolean isPrinted  = false;
        for (int i = 0 ; i < b.length ; i++) {
            String temp="";
            int x=i;
            for(int j = 0 ; j < b.length ; j++) {
                int y = j;
                while (x >= 0 && y < b.length) {
                    isPrinted = false;
                    temp+=b[x--][y++];                  
                }
                if(!isPrinted) {
                    System.out.println(temp);
                    isPrinted = true;
                }
            }
        }
    }

- Aditya

1

类型1：我们可以很容易地使用Python解决这个问题

代码：

r,c=map(int,input().split())
mat=[[str(ch) for ch in input().split()]for _ in range(r)]
for i in range(r*c-2):
    lis=[]
    for j in range(r):
        for k in range(c):
            if k+j==i:
                lis.append(mat[j][k])
    print(*lis[::-1])

输出：

5 5
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y

a
f b
k g c
p l h d
u q m i e
v r n j
w s o
x t
y

- Surya P

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicolai · Accepted Answer

仅用于测试目的初始化数组：

int dim = 5;
char ch = 'A';
String[][] array = new String[dim][];
for( int i = 0 ; i < dim ; i++ ) {
    array[i] = new String[dim];
    for( int j = 0 ; j < dim ; j++, ch++ ) {
        array[i][j] = "" + ch;
    }
}

输出我们的矩阵：

for( int i = 0 ; i < dim ; i++ ) {
    for( int j = 0 ; j < dim ; j++, ch++ ) {
        System.out.print( array[i][j] + " " );
    }
    System.out.println();
}
System.out.println( "============================" );

解决方案

对角线上的元素索引有一个规则 - 它们在一条对角线上的和是恒定的：

变体1

使用两个循环来提取所有对角线。

第一个循环提取对角线的上半部分：

for( int k = 0 ; k < dim ; k++ ) {
    for( int j = 0 ; j <= k ; j++ ) {
        int i = k - j;
        System.out.print( array[i][j] + " " );
    }
    System.out.println();
}

第二个循环迭代对角线的下半部分：

for( int k = dim - 2 ; k >= 0 ; k-- ) {
    for( int j = 0 ; j <= k ; j++ ) {
        int i = k - j;
        System.out.print( array[dim - j - 1][dim - i - 1] + " " );
    }
    System.out.println();
}

变量2

使用一个循环来提取所有对角线，但是会有额外的迭代和一个额外的检查：

for( int k = 0 ; k < dim * 2 ; k++ ) {
    for( int j = 0 ; j <= k ; j++ ) {
        int i = k - j;
        if( i < dim && j < dim ) {
            System.out.print( array[i][j] + " " );
        }
    }
    System.out.println();
}

输出：

A B C D E 
F G H I J 
K L M N O 
P Q R S T 
U V W X Y 
============================
A 
F B 
K G C 
P L H D 
U Q M I E 
V R N J 
W S O 
X T 
Y

更新

在评论中有关于矩形矩阵（高度 != 宽度）的问题。这里是矩形矩阵的解决方案：

规则仍然相同：同一对角线上元素索引之和是恒定的

索引之和的最小值为0（对于具有索引[0;0]的矩阵中的第一个元素）

索引之和的最大值为width + height - 2（对于具有索引[height-1; with-1]的矩阵中的最后一个元素）

仅出于测试目的初始化矩形矩阵：

int WIDTH = 7;
int HEIGHT = 3;
char ch = 'A';
String[][] array = new String[HEIGHT][];
for( int i = 0 ; i < HEIGHT ; i++ ) {
    array[i] = new String[WIDTH];
    for( int j = 0 ; j < WIDTH ; j++, ch++ ) {
        array[i][j] = "" + ch;
    }
}

打印我们的矩形矩阵：

for( int i = 0 ; i < HEIGHT ; i++ ) {
    for( int j = 0 ; j < WIDTH ; j++, ch++ ) {
        System.out.print( array[i][j] + " " );
    }
    System.out.println();
}
System.out.println( "============================" );

解决方案

for( int k = 0 ; k <= WIDTH + HEIGHT - 2; k++ ) {
    for( int j = 0 ; j <= k ; j++ ) {
        int i = k - j;
        if( i < HEIGHT && j < WIDTH ) {
            System.out.print( array[i][j] + " " );
        }
    }
    System.out.println();
}

输出：

A B C D E F G 
H I J K L M N 
O P Q R S T U 
============================
A 
H B 
O I C 
P J D 
Q K E 
R L F 
S M G 
T N 
U