矩阵基础
- 使用哈希数组来标记当前行或者列是否出现0
- 按层模拟
- 旋转90度可以先水平翻，然后再对角线翻
- 二分查找
- 从右上角Z字形缩减矩阵
73. 矩阵置零
题目讲解：LeetCode
重点：
- 使用标记数组：用两个标记数组分别记录每一行和每一列是否有零出现。
- 使用两个标记变量：用矩阵的第一行和第一列代替两个标记数组。再额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
思路：
- 使用标记数组
1.首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。
2.最后我们再次遍历该数组，用标记数组更新原数组即可。- 使用两个标记变量
1.首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列。
2.然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。复杂度：
- m 是矩阵的行数，n 是矩阵的列数
- 使用标记数组
时间复杂度：O(mn)
空间复杂度：O(m+n)- 使用两个标记变量
时间复杂度：O(mn)
空间复杂度：O(1)
// 使用标记数组
public void setZeroes(int[][] matrix) {
// 重点: 用两个标记数组分别记录每一行和每一列是否有零出现
boolean[] row = new boolean[matrix.length];
boolean[] col = new boolean[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (row[i] || col[j]) matrix[i][j] = 0;
}
}
}
// 使用两个标记变量
public void setZeroes(int[][] matrix) {
boolean row0Flag = false;
boolean col0Flag = false;
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
row0Flag = true;
break;
}
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
col0Flag = true;
break;
}
}
// 重点: 使用第一行和第一列标记
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
// 重点: 再用两个标记变量处理第一行和第一列
if (row0Flag) {
Arrays.fill(matrix[0], 0);
}
if (col0Flag) {
for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0;
}
}
54. 螺旋矩阵
题目讲解：LeetCode
重点：
- 按层模拟。四个标记。
思路：
- 按层模拟
1.每一层遍历 顶 右 底 左。每遍历完一个对应的边界需要处理。复杂度：
- m 和 n 分别是行数和列数
- 时间复杂度：O(mn)。每个元素都要被访问一次。
- 空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int curTop = 0;
int curRight = matrix[0].length - 1;
int curBottom = matrix.length - 1;
int curLeft = 0;
// 重点: 按层模拟, 每一层遍历 顶 右 底 左
while (curLeft <= curRight && curTop <= curBottom) {
// 当前层的最顶行
for (int i = curLeft; i <= curRight; i++) {
result.add(matrix[curTop][i]);
}
curTop++;
// 当前层的最右列
for (int i = curTop; i <= curBottom; i++) {
result.add(matrix[i][curRight]);
}
curRight--;
// 当前外层的最底行还存在
if (curTop <= curBottom) {
for (int i = curRight; i >= curLeft; i--) {
result.add(matrix[curBottom][i]);
}
}
curBottom--;
// 当前外层的最左列还存在
if (curLeft <= curRight) {
for (int i = curBottom; i >= curTop; i--) {
result.add(matrix[i][curLeft]);
}
}
curLeft++;
}
return result;
}
48. 旋转图像
题目讲解：LeetCode
重点：
- 原地旋转代码背下来。
- 用翻转代替旋转。水平翻，然后对角线翻。
思路：
- 原地旋转
- 逆时间的顺序来替换。背下来。
- 用翻转代替旋转
- 先水平翻转
- 再对角线翻转
复杂度：
- N 是 matrix 的边长
- 原地旋转
时间复杂度：O(N^2)
空间复杂度：O(1)- 用翻转代替旋转
时间复杂度：O(N^2)
空间复杂度：O(1)
// 原地旋转
public void rotate(int[][] matrix) {
int n = matrix.length;
// 替换一半另一半就相当于自动替换过去了
for (int i = 0; i < n / 2; i++) {
// 内层要加一是因为n为奇数时需要多遍历一遍
for (int j = 0; j < (n + 1) / 2; j++) {
int temp = matrix[i][j];
// 逆时针替换
// 左上
matrix[i][j] = matrix[n - j - 1][i];
// 左下
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
// 右下
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
// 右上
matrix[j][n - i - 1] = temp;
}
}
}
// 用翻转代替旋转
public void rotate(int[][] matrix) {
int n = matrix.length;
// 重点: 先水平翻转
for (int i = 0; i < matrix.length / 2; i++) {
for (int j = 0; j < matrix[0].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 重点: 再对角线翻转, 循环条件看作楼梯, 外层循环i=0则为对角线左侧楼梯顶层
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
240. 搜索二维矩阵 II
题目讲解：LeetCode
重点：
- 二分查找
- 从右上角开始Z字形缩减矩阵
思路：
- 二分查找
- 每一行的元素都是升序排列的，因此可以对每一行都使用二分查找
- Z字形缩减矩阵
- 从矩阵的右上角开始搜索
- 在每一步的搜索过程中，我们希望在以矩阵的左下角为左下角、以 (x,y) 为右上角的矩阵中进行搜索
- 如果等于，说明搜索完成。
如果大于，因为是右上角，所以当前列肯定都大于了，舍弃列。
如果小于，因为是右上角，所以当前行肯定都小于了，舍弃行。复杂度：
- m是行，n是列
- 二分查找
时间复杂度：O(mlogn)。总共m行，每次二分查找要logn。
空间复杂度：O(1)- Z字形缩减矩阵
时间复杂度：O(m+n)。y 最多能被减少 n 次，x 最多能被增加 m 次，总搜索次数为 m+n。
空间复杂度：O(1)
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
int targetIndex = binarySearch(row, target);
if (targetIndex >= 0) return true;
}
return false;
}
// 对当前行进行二分查找
public int binarySearch(int[] row, int target) {
int low = 0, high = row.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = row[mid];
if (num == target) return mid;
else if (num > target) high = mid - 1;
else low = mid + 1;
}
return -1;
}
// Z字形缩减矩阵
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
// 从矩阵右上角开始缩小矩阵
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) return true;
if (matrix[x][y] > target) y--;
else x++;
}
return false;
}