240.搜索二维矩阵②
编写一个高效的算法来搜索 mxn 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
-
每行的元素从左到右升序排列。
-
每列的元素从上到下升序排列。
思路：
-
输入矩阵：
-
搜索目标值：
-
使用从右上角开始的搜索策略：
-
如果当前值等于目标值，返回
true。 -
如果当前值大于目标值，向左移动（列减1）。
-
如果当前值小于目标值，向下移动（行加1）。
-
-
如果超出矩阵边界仍未找到目标值，返回
false。
-
java">import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入矩阵的行数和列数int n = scanner.nextInt();int m = scanner.nextInt();// 输入矩阵的元素int[][] matrix = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = scanner.nextInt();}}// 输入目标值int target = scanner.nextInt();// 调用 searchMatrix 方法搜索目标值boolean result = searchMatrix(matrix, target);// 输出结果System.out.println(result ? "true" : "false");}/*** 在有序矩阵中搜索目标值* @param matrix 有序矩阵* @param target 目标值* @return 是否找到目标值*/public static boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length; // 行数int m = matrix[0].length; // 列数int row = 0; // 初始化行指针为第一行int col = m - 1; // 初始化列指针为最后一列while (row < n && col >= 0) {if (matrix[row][col] == target) {return true;} // 如果当前元素大于目标值，说明目标值可能在当前列的左边else if (matrix[row][col] > target) {col--; // 向左移动} else {row++; // 向下移动}}return false;}
}
73. 矩阵置零
给定一个 mxn 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
思路：
遍历矩阵的每个元素，找到所有需要置零的行和列，遍历 row 列表中的每个行索引将记录的行置零，遍历 coloum 列表中的每个列索引将该列的所有元素置为 0。
java">class Solution {public void setZeroes(int[][] matrix) {int n = matrix.length; // 行数int m = matrix[0].length; // 列数
// 使用两个列表分别记录需要置零的行索引和列索引List<Integer> row = new ArrayList<>(); // 存储需要置零的行索引List<Integer> coloum = new ArrayList<>(); // 存储需要置零的列索引
// 遍历矩阵，找到所有值为0的元素，并记录它们所在的行和列索引for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == 0) { row.add(i); // 记录该行索引coloum.add(j); // 记录该列索引}}}
// 遍历记录的行索引，将对应行的所有元素置为0for (Integer r : row) {for (int i = 0; i < m; i++) {matrix[r][i] = 0; }}
// 遍历记录的列索引，将对应列的所有元素置为0for (Integer c : coloum) {for (int i = 0; i < n; i++) { matrix[i][c] = 0; }}}
}优化：利用矩阵的第一行和第一列记录需要置零的行和列，避免了额外的空间开销，同时保持了时间复杂度为 O(n×m)。这种方法在处理大规模矩阵时尤其高效。
java">class Solution {public void setZeroes(int[][] matrix) {int n = matrix.length; // 行数int m = matrix[0].length; // 列数
boolean firstRowZero = false; // 标记第一行是否需要置零boolean firstColZero = false; // 标记第一列是否需要置零
// 遍历矩阵，记录需要置零的行和列for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == 0) {// 如果第一行有0，标记第一行需要置零if (i == 0) {firstRowZero = true;}// 如果第一列有0，标记第一列需要置零if (j == 0) {firstColZero = true;}// 使用第一行和第一列记录需要置零的行和列matrix[i][0] = 0;matrix[0][j] = 0;}}}
// 根据第一行和第一列的标记，置零对应的行和列// 跳过第一行和第一列，避免重复置零for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}
// 如果第一行需要置零if (firstRowZero) {for (int j = 0; j < m; j++) {matrix[0][j] = 0;}}
// 如果第一列需要置零if (firstColZero) {for (int i = 0; i < n; i++) {matrix[i][0] = 0;}}}
}54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
思路：记录四个变量上下左右的边界值，每次循环走四条边。
java">class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>(); // 用于存储螺旋顺序的结果
int left = 0; // 左边界int top = 0; // 上边界int down = matrix.length - 1; // 下边界int right = matrix[0].length - 1; // 右边界
// 当左边界小于等于右边界，且上边界小于等于下边界时，继续循环while (left <= right || top <= down) {// 从左到右遍历上边界for (int i = left; i <= right && top <= down; i++) {list.add(matrix[top][i]); }top++; // 上边界下移
// 从上到下遍历右边界for (int i = top; i <= down && left <= right; i++) {list.add(matrix[i][right]); }right--; // 右边界左移
// 从右到左遍历下边界for (int i = right; i >= left && top <= down; i--) {list.add(matrix[down][i]); }down--; // 下边界上移
// 从下到上遍历左边界for (int i = down; i >= top && left <= right; i--) {list.add(matrix[i][left]); }left++; // 左边界右移}
return list; }
}48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
思路：
1. 上下翻转矩阵
-
目的：将矩阵的第一行与最后一行交换，第二行与倒数第二行交换，依此类推。
-
实现：
-
使用一个临时数组
temp保存当前行。 -
将当前行替换为对应的倒数行。
-
将倒数行替换为临时数组
temp。
-
2. 转置矩阵
-
目的：将矩阵的行和列互换，即
matrix[i][j]和matrix[j][i]互换。 -
实现：
-
遍历矩阵的上三角部分（
j < i），因为下三角部分会在转置过程中被覆盖。 -
使用一个临时变量
temp保存当前元素。 -
交换
matrix[i][j]和matrix[j][i]
-
java">class Solution {public void rotate(int[][] matrix) {int n = matrix.length; // 获取矩阵的大小
// 第一步：上下翻转矩阵// 将矩阵的第一行与最后一行交换，第二行与倒数第二行交换，依此类推for (int i = 0; i < n / 2; i++) {int[] temp = matrix[i]; // 临时存储当前行matrix[i] = matrix[n - i - 1]; // 将当前行替换为对应的倒数行matrix[n - i - 1] = temp; // 将倒数行替换为临时存储的当前行}
// 第二步：转置矩阵// 将矩阵的行和列互换，即 matrix[i][j] 和 matrix[j][i] 互换for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) { // 只需遍历矩阵的上三角部分int temp = matrix[i][j]; // 临时存储当前元素matrix[i][j] = matrix[j][i]; // 将当前元素替换为对应的转置元素matrix[j][i] = temp; // 将转置元素替换为临时存储的当前元素}}}
}
