hot100-矩阵
240.搜索二维矩阵②
编写一个高效的算法来搜索 mxn 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
-
每行的元素从左到右升序排列。
-
每列的元素从上到下升序排列。
思路：
-
输入矩阵：
-
从标准输入读取矩阵的行数
n和列数m。 -
按行输入矩阵的元素。
-
-
搜索目标值：
-
使用从右上角开始的搜索策略：
-
如果当前值等于目标值，返回
true。 -
如果当前值大于目标值，向左移动（列减1）。
-
如果当前值小于目标值，向下移动（行加1）。
-
-
如果超出矩阵边界仍未找到目标值，返回
false。
-
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。
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); // 记录该列索引
}
}
}
// 遍历记录的行索引，将对应行的所有元素置为0
for (Integer r : row) {
for (int i = 0; i < m; i++) {
matrix[r][i] = 0;
}
}
// 遍历记录的列索引，将对应列的所有元素置为0
for (Integer c : coloum) {
for (int i = 0; i < n; i++) {
matrix[i][c] = 0;
}
}
}
}优化：利用矩阵的第一行和第一列记录需要置零的行和列，避免了额外的空间开销，同时保持了时间复杂度为 O(n×m)。这种方法在处理大规模矩阵时尤其高效。
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 ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
思路：记录四个变量上下左右的边界值，每次循环走四条边。
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]
-
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; // 将转置元素替换为临时存储的当前元素
}
}
}
}