一、矩阵置零
中等
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地↗ 算法
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
进阶：
- 一个直观的解决方案是使用
O(mn)的额外空间，但这并不是一个好的解决方案。 - 一个简单的改进方案是使用
O(m + n)的额外空间，但这仍然不是最好的解决方案。 - 你能想出一个仅使用常量空间的解决方案吗？
1.1 用集合记录每个零点的坐标
class Solution {
/**
* 73. 矩阵置零（记录每个零点坐标，O(mn)）
*
* @param matrix 矩阵
*/
private int m, n;
public void setZeroes(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
List<int[]> zeros = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) zeros.add(new int[]{i, j});
}
}
for (int[] zs : zeros) update(matrix, zs[0], zs[1]);
}
private void update(int[][] matrix, int i, int j) {
for (int x = 0; x < m; x++) matrix[x][j] = 0;
for (int y = 0; y < n; y++) matrix[i][y] = 0;
}
}最坏情况下，整个矩阵都是0，zeors长度为mn
1.2 仅用数组记录行列
class Solution {
/**
* 73. 矩阵置零（记录每个零点行号和列号，O(m + n)）
*
* @param matrix 矩阵
*/
private int m, n;
public void setZeroes(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
int[] mi = new int[m];
int[] nj = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
mi[i] = 1;
nj[j] = 1;
}
}
}
for (int i = 0; i < m; i++)
if (mi[i] == 1) updateRow(matrix, i);
for (int j = 0; j < n; j++)
if (nj[j] == 1) updateCol(matrix, j);
}
private void updateRow(int[][] matrix, int i) {
for (int y = 0; y < n; y++) matrix[i][y] = 0;
}
private void updateCol(int[][] matrix, int j) {
for (int x = 0; x < m; x++) matrix[x][j] = 0;
}
}仅仅标记哪一行和哪一列有0，空间复杂度恒为O(m + n)
1.3 用原矩阵第一行第一列来记录行列
1.2 中用了额外的数组来记录行列，既然我们要修改原矩阵，倘若某一行/列有0，那么这一行/列的首个元素一定会被设为0
因此我们可以直接利用矩阵的第一行和第一列来充当mi[]和nj[]
class Solution {
/**
* 73. 矩阵置零（用原矩阵第一行第一列来记录行列，O(1)）
*
* @param matrix 矩阵
*/
private int m, n;
public void setZeroes(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
// 确认第一行第一列是否包含0
boolean firstRow = false, firstCol = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstCol = true;
break;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRow = true;
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++)
if (matrix[i][0] == 0) updateRow(matrix, i);
for (int j = 1; j < n; j++)
if (matrix[0][j] == 0) updateCol(matrix, j);
if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
private void updateRow(int[][] matrix, int i) {
for (int y = 0; y < n; y++) matrix[i][y] = 0;
}
private void updateCol(int[][] matrix, int j) {
for (int x = 0; x < m; x++) matrix[x][j] = 0;
}
}二、螺旋矩阵
中等
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
2.1 标记 + 轮询
❓如何螺旋遍历
对于点(i, j)，移动一步，可以写成：
i += DIRS[round][0];j += DIRS[round][1];
其中DIRS为方向数组{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}，依次表示向右、向下、向左、向上走
❓如何转弯
碰到墙壁就转弯，有四个方向，故周期为4，取模4，即轮询方向数组的四个元素
❓如何确定碰到了墙壁
矩阵本身边界为墙壁，已访问过的元素也变成墙壁
注意到-100 <= matrix[i][j] <= 100，故可以把遍历过的元素设为101，表示已访问过
class Solution {
// 右下左上
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
/**
* 54. 螺旋矩阵（标记）
*
* @param matrix 矩阵
* @return 螺旋遍历的结果
*/
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
List<Integer> ans = new ArrayList<>();
int i = 0, j = 0, round = 0;
for (int k = 0; k < m * n; k++) {
ans.add(matrix[i][j]);
// 标记为墙壁
matrix[i][j] = 101;
int x = i + DIRS[round][0];
int y = j + DIRS[round][1];
// 判断是否碰到了墙壁
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == 101) {
round = (round + 1) % 4;
}
// 移动
i += DIRS[round][0];
j += DIRS[round][1];
}
return ans;
}
}2.2 收缩
如果题目要求不能修改原数组，那么就不能采用2.1原地哈希的方式来操作
❓2.1 是把已访问过的元素改为无穷大（变成墙壁），那现在怎么办
注意到矩阵初始自带四个墙壁（边界），既然不能手动造墙壁，那可以直接移动这四个墙壁
上墙壁u（up），下墙壁d（down），左墙壁l（left），右墙壁r（right）
- 从左到右：上边一行遍历完了，移动上墙壁
u - 从上到下：右边一列遍历完了，移动右墙壁
r - 从右到左：下边一行遍历完了，移动下墙壁
d - 从下到上：左边一列遍历完了，移动左墙壁
l - 回到 1. 从左到右
class Solution {
/**
* 54. 螺旋矩阵（四边界收缩）
*
* @param matrix 矩阵
* @return 螺旋遍历的结果
*/
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
// 上up，下down，左left，右right
int u = 0, d = m - 1, l = 0, r = n - 1;
for (int k = 0; k < m * n;) {
// 向右走
for (int j = l; j <= r && k++ < m * n; j++)
ans.add(matrix[u][j]);
u++;
// 向下走
for (int i = u; i <= d && k++ < m * n; i++)
ans.add(matrix[i][r]);
r--;
// 向左走
for (int j = r; j >= l && k++ < m * n; j--)
ans.add(matrix[d][j]);
d--;
// 向上走
for (int i = d; i >= u && k++ < m * n; i--)
ans.add(matrix[i][l]);
l++;
}
return ans;
}
}2.3 简化收缩
在第一次向右走的时候，需要遍历n个元素
在第一次向下走的时候，需要遍历m个元素
在第一次向左走的时候，需要遍历n - 1个元素
在第一次向上走的时候，需要遍历m - 1个元素
在第二次向右走的时候，需要遍历n - 2个元素
在第二次向下走的时候，需要遍历m - 2个元素
…
可以发现，在一个方向上移动时，只需要关注对应方向的长度，而另一个方向的长度是不需要关心的
因此可以用m和n来控制转弯，不用四面墙壁，只需要遍历 上次这个方向的遍历次数 - 1 次就可以转弯
由于每次都有一个方向的长度不被关心，我们可以轮转交替两个方向的长度
0x3f 灵神的题解中这样子描述
从 (0,−1) 开始，一开始走 n 步
把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 m−1 步），无需修改其他逻辑
把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 n−1 步）
把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 m−2 步）
依此类推，每次只需把 n,m 分别更新为 m−1,n 即可。
class Solution {
// 右下左上
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
/**
* 54. 螺旋矩阵（收缩）
*
* @param matrix 矩阵
* @return 螺旋遍历的结果
*/
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
List<Integer> ans = new ArrayList<>();
int i = 0, j = -1, round = 0;
int end = m * n;
for (; ans.size() < end; round = (round + 1) % 4) {
for(int k = 0; k < n; k++) {
i += DIRS[round][0];
j += DIRS[round][1];
ans.add(matrix[i][j]);
}
int temp = n;
n = m - 1;
m = temp;
}
return ans;
}
}三、旋转图像
中等
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地↗ 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
3.1 转置 + 翻转
旋转顺时针90度的本质
如果原始矩阵是
matrix[i][j]，旋转后的位置应该变成：matrix[i][j] => matrix[j][n-1-i]也就是第 i 行第 j 列的元素，会变到第 j 行第 (n-1-i) 列的位置
可以先转置矩阵，再行翻转
转置：matrix[i][j] => matrix[j][i]
- 把元素上下对角线对称地互换，行变列，列变行。
- 原本
(i, j)->(j, i) - 得到原矩阵的“镜像”版本。
行翻转：把 row[j] 和 row[n-1-j] 对调，即matrix[j][i] => matrix[j][n-1-i]
class Solution {
/**
* 54. 螺旋矩阵（转置 + 翻转）
*
* @param matrix 矩阵
*/
public void rotate(int[][] matrix) {
int n = matrix.length;
// 第一步：转置
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { // 遍历对角线下方元素
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// 第二步：行翻转
for (int[] row : matrix) {
for (int j = 0; j < n / 2; j++) { // 遍历左半元素
int tmp = row[j];
row[j] = row[n - 1 - j];
row[n - 1 - j] = tmp;
}
}
}
}3.2 四点旋转
❓3.1 中提到matrix[i][j] => matrix[j][n-1-i]，能不能一步到位
1 2 3 4 x 2 x x
5 6 7 8 只看其中4个点 x x x 8
9 10 11 12 ============> 9 x x x
13 14 15 16 x x 15 x对于每个小矩形，其实就是这四个点在轮转
👇图蓝色部分 => 绿色部分 => 红色部分 => 黄色部分 => 蓝色部分
class Solution {
/**
* 54. 螺旋矩阵（四点旋转）
*
* @param matrix 矩阵
*/
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) { // i 是环层
for (int j = 0; j < (n + 1) / 2; j++) { // j 是环内元素
// 四点坐标
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
}四、搜索二维矩阵 II
中等
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
4.1 收缩
收缩的目的是：朝一个方向移动，去掉的元素要么都比目标值大，要么都比目标值小
对于一维单增数组进行二分查找中，每次去掉的一半要么都比
target大，要么懂比target小
本题中，只有左下角和右上角满足，每次朝一个方向移动可以砍掉一条边，👇图源（灵神题解）
class Solution {
/**
* 240. 搜索二维矩阵 II（收缩）
*
* @param matrix 矩阵
* @param target 目标值
* @return 目标值是否存在
*/
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) j--;
else i++;
}
return false;
}
}时间复杂度：O(m+n)
空间复杂度：O(1)