【每日算法Day 42】矩阵2
关于矩阵比较难的题目一般会出在利用矩阵来模拟图进行路径查找，这类问题往往涉及到DFS。
# LeetCode 73. 矩阵置零 (opens new window)
# 题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
# 示例
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
2
3
4
5
6
7
8
9
10
11
12
# 解题思路
在遍历矩阵时由于不能遇到一个0就立即把对应的行列置为0（会导致最终全为0），那么可以用额外的两个set记录需要置0的行和列，扫描一遍矩阵之后再进行置0。如果第二次扫描时的点的行或者列在set内就置为0。
public void setZeroes(int[][] matrix) {
if (matrix==null) return;
Set<Integer> rows = new HashSet<>(), cols = new HashSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (rows.contains(i)||cols.contains(j))
matrix[i][j]=0;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
这样做没有使用原地算法，为此可以在第一遍扫描遇到0时把该元素所在行列的行首和列首置为一个非0的标记值如Integer.MIN_VALUE，第二次扫描时如果行首或列首为标记值或0就把该元素置为0。不过这样做其实不够严谨，如果矩阵中原来有标记值结果就不正确了。对于非强类型的语言数组中的标记可以使用字符串代替，但是强类型语言就不可以这样做。
# LeetCode 329. 矩阵中的最长递增路径 (opens new window)
# 题目描述
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
# 示例
输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
2
3
4
5
6
7
8
# 解题思路
遍历矩阵中的每一个点，以该点为起始点进行DFS搜索计算最长递增路径的长度，DFS的终止条件是该点四个方向上都没有更大节点了。另外，使用一个同等的数组存储每一个点开始的最长路径长度，如果下一个节点有对应的结果使用该结果就可以了，这样进行DFS时就省掉了重复的遍历过程。
public class No329_LongestIncreasingPathInAMatrix {
//存储要dfs的方向，使用数组来简化代码
private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int rows, cols;
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
rows = matrix.length;
cols = matrix[0].length;
int[][] result = new int[rows][cols];
int max=0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
max = Math.max(max, dfs(matrix, i, j, result));
}
}
return max;
}
private int dfs(int[][] matrix, int row, int col, int[][]result) {
if(result[row][col]!=0) return result[row][col];
for (int[] dir : directions) {
int x = row + dir[0], y = col + dir[1];
if (0 <= x && x < rows && 0 <= y && y < cols && matrix[row][col] < matrix[x][y]) {
result[row][col] = Math.max(result[row][col], dfs(matrix, x, y, result));
}
}
return ++result[row][col];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# LeetCode 378. 有序矩阵中第K小的元素 (opens new window)
# 题目描述
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
# 示例
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
2
3
4
5
6
7
8
# 解题思路
简单直接的思路可能是创建一个O(n^2)大小的一维数组存储矩阵中的值，然后对其进行进行排序就可以了，排序的时间复杂度为O(n*2logn)。
另一种思路是对矩阵中的所有行进行归并排序，不过一般的归并排序是对两个数组进行排序，这里的排序是同时对n个数组进行排序，需要用一个小顶堆维护，具体思路方法可以参考LeetCode 23. 合并K个排序链表 (opens new window)。时间复杂度为O(klongn)，归并k次，空间复杂度为O(n)。
观察矩阵，最小值在左上角，最大值在右下角。对于最大值和最小值之间的任意数mid，我们总能找到一条边界使得边界左上方的值小于等于mid、右下方的值大于mid，沿着边界走一遍我们就能在线性时间内计算出不大于mid的数字的数量count。如果count>=k则说明最终答案不会超过mid，如果count<k则最终答案一定大于mid。就这样进行二分查找，直到左右边界相同。
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left < right) {
int mid = left + ((right - left) >> 1);
//如果小于等于mid的数的数目count>=k，则第k小的数的大小不可能超过mid（有可能等于mid）
if (getCount(matrix,mid,n)>=k) {
right = mid;
} else {//否则第k小的数一定大于mid
left = mid + 1;
}
}
return left;
}
private int getCount(int[][] matrix, int mid, int n) {
int i = n - 1, j = 0, count = 0;
while (i >= 0 && j <= n - 1) {
if (matrix[i][j] <= mid) {
count += i + 1;
j++;
} else {
i--;
}
}
return count;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
二分查找采用了闭区间搜索，唯一要注意的是终止条件不是left=right+1，而是left=right就限定了目标数的唯一取值，目标数一定存在。