本文共 3702 字,大约阅读时间需要 12 分钟。
JAVA算法:回形矩阵输出
题目要求
给定一个整形矩阵Matrix,请按照顺时针方向转圈的方式,输入(打印)元素值。 例如: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输出结果为: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7算法设计
package com.bean.algorithmexec;public class MatrixDemo { /* * 给定一个整形矩阵Matrix,请按照顺时针方向转圈的方式,输入(打印)元素值。 * 例如: * 1 2 3 4 * 5 6 7 8 * 9 10 11 12 * 13 14 15 16 * 输出结果为: * 1 2 3 4 * 12 13 14 5 * 11 16 15 6 * 10 9 8 7 * * 要求:额外空间复杂度为O(1) * */ /* * 转圈打印矩阵元素(顺时针转圈) * */ public static int[][] generateMatrix(int n) { int[][] rs = new int[n][n]; int top = 0,bottom = n-1,left = 0,right = n-1; int num = 1; //边界条件是 left<=right 同时 top<=bottom while(left<=right && top <=bottom){ /* * 从左向右 * 初次,当left=0时,rs[top][i]表示第一行的元素, * i=left=0;赋值之后 i++,表示从第一行第一列的元素到第一行最后一个元素依次赋值, * 然后top++,表示下移一行,到第二行。 * */ for(int i=left;i<=right;i++){ rs[top][i] = num++; } top++;//向下移动一行 /* * 从上到下 * 当i=1,i<=bottom;i++ * rs[i][right]表示从rs[1][n-1]到rs[n-1][n-1]依次赋值, * 即为矩阵最右边一列元素,从上到下依次赋值 * 然后right--表示将最后一列列赋值之后数组下标依次向倒数第二列,倒数第三列移动 * */ for(int i= top;i<=bottom;i++){ rs[i][right] = num++; } right--; /* * 从右向左 * i从倒数第二列开始,当i>=left;i-- * rs[bottom][i]表示从矩阵的最后一行的倒数第二个元素开始依次从右向左赋值并移动 * bottom--,表示赋值之后从下向上移动一行 * * */ for(int i= right;i>=left;i-- ){ rs[bottom][i] = num++; } bottom--; /* * 从下向上 * 当i=bottom;i>=top;i-- * 表示从倒数第二行开始依次给最左边的列开始赋值,第一次赋值时left=0,代表矩阵的第一列 * 当left++后,表示移动到矩阵的第二列 * */ for(int i = bottom;i>=top;i--){ rs[i][left] = num++; } left++; } return rs; } public static void main(String[] args) { // TODO Auto-generated method stub //初始化一个 4*4的整形矩阵,从第一行第一列从左向右,第二行,第三行,直到第四行依次赋值 1,2,...16. int[][] matrixDemo=new int[4][4]; matrixDemo=createMatrix(); printMatrix(matrixDemo); //转圈打印 spiralOrderPrint(matrixDemo); System.out.println("第二种算法设计"); int[][] result=generateMatrix(4); printMatrix(result); } /* * 创建初始矩阵 * */ private static int[][] createMatrix() { // TODO Auto-generated method stub int matrix[][]=new int[4][4]; int k=1; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { matrix[i][j]=k; k++; } } return matrix; } //顺序打印矩阵元素 private static void printMatrix(int[][] matrix) { for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { System.out.print(matrix[i][j]+"\t"); } System.out.println(); } } //转圈打印 private static void spiralOrderPrint(int[][] matrix) { int tR=0; int tC=0; int dR=matrix.length-1; int dC=matrix[0].length-1; while(tR<=dR && tC<=dC) { printEdge(matrix, tR++, tC++, dR--,dC--); } } private static void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) { // TODO Auto-generated method stub if(tR==dR) { //子矩阵只有一行时 for(int i=tC;i<=dC;i++) { System.out.print(matrix[tR][i]+" "); } }else if(tC==dC) { //子矩阵只有一列时 for(int i=tR;i<=dR;i++){ System.out.print(matrix[i][tC]+" "); } }else { //一般情况 int curC=tC; int curR=tR; while(curC!= dC) { System.out.print(matrix[tR][curC]+" "); curC++; } while(curR!= dR) { System.out.print(matrix[curR][dC]+" "); curR++; } while(curC!= tC) { System.out.print(matrix[dR][curC]+" "); curC--; } while(curR!= tR) { System.out.print(matrix[curR][tC]+" "); curR--; } } } }
转载地址:http://rntdi.baihongyu.com/