Java 对角循环遍历二维数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20420065/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Loop diagonally through two dimensional array
提问by user243872
I wrote the following code to walk half the diagonals of an array:
我编写了以下代码来遍历数组的一半对角线：
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);
}
}
Right now it prints the diagonals i.e current output:
现在它打印对角线，即当前输出：
g dh aei bf c
How do I make it print the other half diagonals i.e required output:
如何让它打印另一半对角线，即所需的输出：
a db gec hf i
回答by alex
Just help yourself, have a look at the indices you need to loop through:
只是帮助自己，看看你需要循环的索引：
#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
Look at the change of the indices in each iteration and create your algorithm. Not so difficult, so do your homework yourself ;)
查看每次迭代中索引的变化并创建您的算法。没那么难，所以自己做功课;)
回答by Aditya
Here is the code:
这是代码：
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;
}
}
}
}
回答by Nicolai
Initialize array only for test purpose:
初始化数组仅用于测试目的：
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;
}
}
Output our matrix:
输出我们的矩阵：
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( "============================" );
Solution
解决方案
Element indexes from diagonals have one rule - their sum is constant on one diagonal:
对角线的元素索引有一个规则——它们的总和在一条对角线上是常数：
VARIANT 1
变体 1
Use two loops to extract all diagonals.
使用两个循环来提取所有对角线。
First loop extracts top half of diagonals:
第一个循环提取对角线的上半部分：
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();
}
Second loop iterates on bottom half of diagonals:
第二个循环在对角线的下半部分迭代：
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();
}
VARIANT 2
变体 2
Use one loop to extract all diagonals, but there are extra iterationsand one additional check:
使用一个循环来提取所有对角线，但有额外的迭代和一项额外的检查：
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();
}
The output:
输出：
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
Update
更新
There are questions about rectangular matrix (height!= width) in comments. Here is solution for rectangular matrix:
评论中有关于矩形矩阵（height!= width）的问题。这是矩形矩阵的解决方案：
The rule remains the same: Sum of element indexes from the same diagonal is constant
规则保持不变：来自同一对角线的元素索引的总和是常数
The minimum sum of indexes is 0(for first element in matrix with indexes [0;0])
索引的最小总和为0（对于索引为 [0;0] 的矩阵中的第一个元素）
The maximum sum of indexes is width + height - 2(for last element in matrix with indexes [height-1; with-1])
索引的最大总和为宽度 + 高度 - 2（对于索引为 [height-1; with-1] 的矩阵中的最后一个元素）
Initialize rectangular matrix only for test purpose:
初始化矩形矩阵仅用于测试目的：
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;
}
}
Print our rectangular matrix:
打印我们的矩形矩阵：
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( "============================" );
Solution
解决方案
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();
}
Output:
输出：
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
回答by AtlasMeh-ed
I wrote the following code. The key is to exhaust all of the diagonals that start at the top and then move onto the diagonals that start on the sides. I included a method that combines the two angles to traverse diagonals Northwest - Southeast and Northeast - Southwest and stand alone methods for traversing the respective angles.
我写了以下代码。关键是用尽从顶部开始的所有对角线，然后移动到从侧面开始的对角线。我包括了一种结合两个角度来遍历对角线西北 - 东南和东北 - 西南的方法，以及用于遍历各个角度的独立方法。
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);
}
}
}
回答by Greg Whittier
This works for non-square arrays. It's simple to understand, but calls min() and max() once per diagonal.
这适用于非方形数组。这很容易理解，但每对角线调用 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("---");
}
Here's output for width=3, height=3
这是宽度 = 3，高度 = 3 的输出
---
0,0
---
0,1
1,0
---
0,2
1,1
2,0
---
1,2
2,1
---
2,2
---
width=3, height=2
宽度=3，高度=2
---
0,0
---
0,1
1,0
---
1,1
2,0
---
2,1
---
width = 2, height = 3
宽度 = 2，高度 = 3
---
0,0
---
0,1
1,0
---
0,2
1,1
---
1,2
---
回答by leoflower
As Alex mentioned here, you need to look into indices in the loop. The following is how I approached this problem.
正如 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);
}
}
回答by Twin
This is the same as what leoflower posted here. I've just changed the variable names for better understanding.
这与 leoflower 在这里发布的内容相同。为了更好地理解，我刚刚更改了变量名称。
level = denotes the current level of the diagonal that is being printed. Ex:- level = 2 denotes diagonal elements with indices (0,2),(1,1),(2,0)
level = 表示正在打印的对角线的当前级别。例如：- level = 2 表示索引为 (0,2),(1,1),(2,0) 的对角元素
currDiagRowIndex = denotes row index of the current diagonal being printed
currDiagRowIndex = 表示正在打印的当前对角线的行索引
currDiagColIndex = denotes columnn index of the current diagonal being printed
currDiagColIndex = 表示正在打印的当前对角线的列索引
void printMatrixDiagonal(int matrix[][], int endRowIndex, int endColIndex){
for(int level = 0; level < endColIndex; level++){
for(int currDiagRowIndex = 0, currDiagColIndex = level; currDiagRowIndex < endRowIndex && currDiagColIndex >= 0 ; currDiagRowIndex++, currDiagColIndex--){
System.out.print(matrix[currDiagRowIndex][currDiagColIndex] + " ");
}
System.out.println();
}
for(int level = 1; level < endRowIndex; level++){
for(int currDiagRowIndex = level, currDiagColIndex = endColIndex-1; currDiagRowIndex < endRowIndex && currDiagColIndex >= 0; currDiagRowIndex++, currDiagColIndex--){
System.out.print(matrix[currDiagRowIndex][currDiagColIndex]+ " ");
}
System.out.println();
}
}
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
Output:
输出：
1
2 6
3 7 11
4 8 12 16
5 9 13 17 21
10 14 18 22
15 19 23
20 24
25
回答by Big O
Solutions would be much easier if we break it down into 2 sub-problems:
如果我们将其分解为 2 个子问题，解决方案会容易得多：
- 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++; } }
- 找出每个对角线的起点。
给定对角线的起始索引，打印对角线。
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++; } }
Print Diagonal: Notice that every time we start printing each diagonal, the index of row should be decremented and the index of column should be incremented. So given the starting indices of each diagonal, we can print the diagonal as follows:
打印对角线：请注意，每次开始打印每个对角线时，行索引应递减，列索引应递增。因此，给定每个对角线的起始索引，我们可以按如下方式打印对角线：
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("");
}
回答by brahmananda Kar
This is very intuitive way to print diagonal matrix in while loop .
这是在 while 循环中打印对角矩阵的非常直观的方法。
generalize the problem as whole rather than two part and optimized in terms of space complexity .
将问题概括为整体而不是两部分，并在空间复杂度方面进行优化。
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");
}
}
}
回答by Shubham Vadhera
This is how:
这是如何：
int [][]mat = { {1,2,3},
{4,5,6},
{7,8,9},
};
int N=3;
for (int s=0; s<N; s++) {
for (int i=s; i>-1; i--) {
System.out.print(mat[i][s-i] + " ");
}
System.out.println();
}
for (int s=1; s<N; s++) {
for (int i=N-1; i>=s; i--) {
System.out.print(mat[i][s+N-1-i] + " ");
}
System.out.println();
}
The first loop prints the diagonals beginning from first column, the second loop prints the remaining diagonals (beginning from bottom row).
第一个循环打印从第一列开始的对角线，第二个循环打印剩余的对角线（从底行开始）。
Output:
输出：
1
4 2
7 5 3
8 6
9
