LeetCode热题100（Java）（6）矩阵

本章包括的题目有：

73. 矩阵置零 - 力扣（LeetCode）

54. 螺旋矩阵 - 力扣（LeetCode）

48. 旋转图像 - 力扣（LeetCode）

240. 搜索二维矩阵 II - 力扣（LeetCode）

1.矩阵置零

思路解析：

有一种简单的思路是创建一个矩阵，标记每个0元素的位置，然后在原矩阵上根据标出来的位置将其行和列置为0。显然，这种思路的空间复杂度是 O(mn) 。当然，我们可以对其进行优化，创建两个数组，在遍历原矩阵的过程中，分别将遍历到的0位置的横纵坐标分别存入对应数组中，由于可能会有相同的横纵坐标，所以我们这里用HashSet去重，可以适当的优化时间效率。

代码实现：

import java.util.ArrayList; import java.util.HashSet; import java.util.Set; class Solution { public void setZeroes(int[][] matrix) { Set<Integer> line = new HashSet<>(); Set<Integer> row = new HashSet<>(); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if(matrix[i][j] == 0){ line.add(i); row.add(j); } } } for(Integer l : line){ for (int i = 0; i < matrix[0].length; i++) { matrix[l][i] = 0; } } for(Integer r : row){ for (int i = 0; i < matrix.length; i++) { matrix[i][r] = 0; } } } }

时间复杂度O（m*n）

空间复杂度O（m + n）

当然，我们也可以原地对其进行标记，得到空间复杂度为 O（1）的方法，可以先定义两个变量，看一下第一行和第一列是否需要被标记为0。然后遍历数组，若某个位置是0，则将其对应的行的第一个和列的第1个位置都标记为0，这样遍历完成之后，再通过第一行和第一列被标记为0的数据去调整整个数组。

如图所示，第一张为原数组，由于第一行有0，所以我们要用一个常量标记第一行，最终要全部置为0，然后将中间位置的0分别将其对应的行列的第一个位置标为0，这样在遍历行的时候，把行对应的所有列标记为0，遍历列的时候，把列对应的所有行标记为0，最后再看常量是否标记第一行和第一列，即可完成整个矩阵的置零操作。

2.螺旋矩阵

思路解析：

螺旋矩阵思路简单，但是代码的细节问题较多，笔者写的时候的思路是，先创建一个矩阵去表示当前位置的值是否被访问过。然后依次向左、向下、向右、向上循环，直到访问到边界，或者访问到被访问过的元素，依次访问完所有元素，即可得到答案。

代码实现：

class Solution { public List<Integer> spiralOrder(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; ArrayList<Integer> ret = new ArrayList<>(); boolean[][] visited = new boolean[m][n]; int i = 0,j = 0; while(m * n != ret.size()){ while(j >= 0 && j < n && i >= 0 && i < m && !visited[i][j]){ ret.add(matrix[i][j]); visited[i][j] = true; j++; if(j >= n || visited[i][j]) { j--; i++; break; } } while(j >= 0 && j < n && i >= 0 && i < m && !visited[i][j]){ ret.add(matrix[i][j]); visited[i][j] = true; i++; if(i >= m || visited[i][j]) { i--; j--; break; } } while(j >= 0 && j < n && i >= 0 && i < m && !visited[i][j]){ ret.add(matrix[i][j]); visited[i][j] = true; j--; if(j < 0 || visited[i][j]) { j++; i--; break; } } while(j >= 0 && j < n && i >= 0 && i < m && !visited[i][j]){ ret.add(matrix[i][j]); visited[i][j] = true; i--; if(i < 0 || visited[i][j]) { i ++; j ++; break; } } } return ret; } }

但是这样写极容易出错，我们可以通过维护四个边界的方式，一步步缩小整个矩阵的搜索范围。维护四个边界：top, bottom, left, right，按顺序打印： 上行：从 left 到 right，然后 top++ ；右列：从 top 到 bottom，然后 right-- ；下行：从 right 到 left，然后 bottom-- ；左列：从 bottom 到 top，然后 left++

代码实现：

class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); if (matrix.length == 0) return res; int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { for (int j = left; j <= right; j++) { res.add(matrix[top][j]); } top++; for (int i = top; i <= bottom; i++) { res.add(matrix[i][right]); } right--; if (top <= bottom) { for (int j = right; j >= left; j--) { res.add(matrix[bottom][j]); } bottom--; } if (left <= right) { for (int i = bottom; i >= top; i--) { res.add(matrix[i][left]); } left++; } } return res; } }

3.旋转图像

思路解析：

我们可以将矩阵层层转置，通过四角轮换的方式

代码实现：

class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { for (int j = i; j < n - 1 - i; j++) { swap(i ,j, matrix); } } } private void swap(int i, int j, int[][] matrix) { //[i][j], [j][len - 1 - i], [len - 1 - i][len - 1 - j], [len - 1 - j][i] int n = matrix.length; int temp = 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] = temp; } }

时间复杂度O（n*n）

空间复杂度O（1）

拓展思路：

也可以通过转置加水平翻转的方式得到结果。先沿对角线将矩阵转置，然后将矩阵水平翻转，即可得到顺时针旋转的结果。

代码实现：

public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][n - 1 - j]; matrix[i][n - 1 - j] = temp; } } }

时间复杂度O（n*n）

空间复杂度O（1）

4.搜索二维矩阵

思路解析：

此题的关键在于我们要从右上角或者从左下角开始，这样的话，我们每次进行选择，就能排除掉一行或者一列。我们拿右上角举例，右上角如果往左走就是变小，往下走就是变大，可以通过对比当前值与目标值的大小，选择往下走或是往左走（类似二叉排序数）。

代码实现：

class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int m = matrix.length; int 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）

上一章：

LeetCode热题100（Java）（5）普通数组-CSDN博客

下一章：

链表（上）