对数器，比较器，矩阵打印问题解析

编程入门行业动态更新时间:2024-10-28 00:28:44

对数器，比较器，矩阵打印问题解析

1：对数器的使用 点击链接
2：认识java中的比较器的使用 点击链接

3:转圈打印矩阵 【题目】给定一个整型矩阵matrix，请按照转圈的方式打印它。例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10 【要求】额外空间复杂度为O(1)。
思想：宏观的思想，看下图。
代码：

public class Code_06_PrintMatrixSpiralOrder {public 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--);}}public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) { //按上图的那个转圈顺序打印if (tR == dR) {for (int i = tC; i <= dC; i++) {System.out.print(m[tR][i] + " ");}} else if (tC == dC) {for (int i = tR; i <= dR; i++) {System.out.print(m[i][tC] + " ");}} else {int curC = tC;int curR = tR;while (curC != dC) {System.out.print(m[tR][curC] + " ");curC++;}while (curR != dR) {System.out.print(m[curR][dC] + " ");curR++;}while (curC != tC) {System.out.print(m[dR][curC] + " ");curC--;}while (curR != tR) {System.out.print(m[curR][tC] + " ");curR--;}}}public static void main(String[] args) {int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },{ 13, 14, 15, 16 } };spiralOrderPrint(matrix);}}

4:旋转正方形矩阵 【题目】给定一个整型正方形矩阵matrix，请把该矩阵调整成顺时针旋转90度的样子。【要求】额外空间复杂度为O(1)。
思想：跟上面的题目相似，其实也就是看几个点的位置是怎么变换的，一个一个框这样子的变换。看下图理解

代码： (注意：此矩形必须是正方形）

public class Code_05_RotateMatrix {public static void rotate(int[][] matrix) {int tR = 0; //第0行int tC = 0;  // 第0列int dR = matrix.length - 1; //dR在第几行（该矩阵的左下角）int dC = matrix[0].length - 1; //dC在第几列（该矩阵的右上角）while (tR < dR) {  //满足交换，因为要看一共有几个子矩阵就要交换几次rotateEdge(matrix, tR++, tC++, dR--, dC--);}}public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) { //隐藏条件，矩形是正方形）int times = dC - tC;   //交换的次数int tmp = 0;for (int i = 0; i != times; i++) { //几个数怎么交换的代码tmp = m[tR][tC + i];m[tR][tC + i] = m[dR - i][tC];m[dR - i][tC] = m[dR][dC - i];m[dR][dC - i] = m[tR + i][dC];m[tR + i][dC] = tmp;}}public static void printMatrix(int[][] matrix) {for (int i = 0; i != matrix.length; i++) {for (int j = 0; j != matrix[0].length; j++) {System.out.print(matrix[i][j] + " ");}System.out.println();}}public static void main(String[] args) {int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },{ 13, 14, 15, 16 } };printMatrix(matrix);rotate(matrix);System.out.println("=========");printMatrix(matrix);}

5：“之”字形打印矩阵 【题目】给定一个矩阵matrix，按照“之”字形的方式打印这个矩阵，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11， 8，12 【要求】额外空间复杂度为O(1)。
思想：也是采用宏观的思想，见下图

代码：

public class Code_08_ZigZagPrintMatrix {public static void printMatrixZigZag(int[][] matrix) {int tR = 0;int tC = 0;int dR = 0;int dC = 0;int endR = matrix.length - 1;//该矩阵的最后一行int endC = matrix[0].length - 1;//该矩阵的最后一列boolean fromUp = false; //用来判断打印的方向while (tR != endR + 1) {printLevel(matrix, tR, tC, dR, dC, fromUp);tR = tC == endC ? tR + 1 : tR;tC = tC == endC ? tC : tC + 1;dC = dR == endR ? dC + 1 : dC;dR = dR == endR ? dR : dR + 1;fromUp = !fromUp;}System.out.println();}public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,boolean f) {  //打印的操作，f是拿来改变打印的方向的变量if (f) {while (tR != dR + 1) {System.out.print(m[tR++][tC--] + " ");}} else {while (dR != tR - 1) {System.out.print(m[dR--][dC++] + " ");}}}public static void main(String[] args) {int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };printMatrixZigZag(matrix);}}

6：在行列都排好序的矩阵中找数 【题目】给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一列都是排好序的。实现一个函数，判断K 是否在matrix中。例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返回false。【要求】时间复杂度为O(N+M)，额外空间复杂度为O(1)。
思想：这道题特殊在他的行和列都是按顺序排好了，所有我们可以从该矩阵的左下角或者右上角依次开始寻找这个数。
代码：

public class Code_09_FindNumInSortedMatrix { //这个矩阵是按从小到大排的顺序public static boolean isContains(int[][] matrix, int K) {int row = 0;int col = matrix[0].length - 1;while (row < matrix.length && col > -1) {if (matrix[row][col] == K) {return true;} else if (matrix[row][col] > K) {  //大于K，就可以从里面的一行开始寻找，因为这个数是这列的最小值col--;} else {row++; //从外面的一列开始寻找}}return false;}public static void main(String[] args) {int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 },// 0{ 10, 12, 13, 15, 16, 17, 18 },// 1{ 23, 24, 25, 26, 27, 28, 29 },// 2{ 44, 45, 46, 47, 48, 49, 50 },// 3{ 65, 66, 67, 68, 69, 70, 71 },// 4{ 96, 97, 98, 99, 100, 111, 122 },// 5{ 166, 176, 186, 187, 190, 195, 200 },// 6{ 233, 243, 321, 341, 356, 370, 380 } // 7};int K = 233;System.out.println(isContains(matrix, K));}}