文章

hot100矩阵题解

发表于 更新于
作者 匆匆那年 15 分钟阅读

560. 矩阵置零

问题描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

img

1
2

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

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.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • $-2^{31} <= matrix[i][j] <= 2^{31} - 1$

进阶：

  • 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

题解

以下是针对问题 560 的 C++ 解答，采用了 常量空间复杂度 的解法：

解题思路

我们可以利用矩阵的第一行和第一列作为标记，记录哪些行和列需要被置零，而不是使用额外的标记数组。这种方法在空间复杂度上是常量的。

步骤：

  1. 使用两个标志变量 rowFlag 和 colFlag，分别标记第一行和第一列是否需要置零。
  2. 遍历矩阵，从第二行和第二列开始，使用第一行和第一列记录需要置零的行和列。
  3. 再次遍历矩阵，根据第一行和第一列的标记，将对应的行和列置零。
  4. 根据 rowFlag 和 colFlag 的值，处理第一行和第一列是否需要置零。

代码实现

1
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <vector>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool rowFlag = false, colFlag = false;

    // Step 1: Check if first row and first column need to be zero
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            colFlag = true;
            break;
        }
    }
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            rowFlag = true;
            break;
        }
    }

    // Step 2: Use first row and first column as markers
    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;
            }
        }
    }

    // Step 3: Zero out cells based on markers
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // Step 4: Zero out first row and column if needed
    if (colFlag) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
    if (rowFlag) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }
}

复杂度分析

  • 时间复杂度: $O(m \times n)$ 遍历矩阵两次，每次都是 $m \times n$ 的规模。
  • 空间复杂度: $O(1)$ 仅使用了两个标志变量和矩阵自身的第一行与第一列作为标记，没有额外的空间开销。

示例运行

输入:

1
2

vector<vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
setZeroes(matrix);

输出:

1

// matrix = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};

这个解法高效且满足常量空间的要求，非常适合在实际问题中使用。

54. 螺旋矩阵

问题描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

1
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.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

题解

以下是针对问题 54 的 C++ 解答，按照顺时针螺旋顺序遍历矩阵。

解题思路

我们可以通过维护四个边界变量 (top, bottom, left, right) 来实现螺旋遍历：

  1. 初始时，top 指向第一行，bottom 指向最后一行，left 指向第一列，right 指向最后一列。
  2. 按顺时针顺序：
    • 从左到右遍历当前顶部行 (top)，然后将 top 下移。
    • 从上到下遍历当前右边列 (right)，然后将 right 左移。
    • 从右到左遍历当前底部行 (bottom)，然后将 bottom 上移（如果未越界）。
    • 从下到上遍历当前左边列 (left)，然后将 left 右移（如果未越界）。
  3. 每次遍历完成后更新边界条件，直到所有元素都被访问。

代码实现

1
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <vector>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty() || matrix[0].empty()) {
        return result;
    }

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right along the top row
        for (int j = left; j <= right; ++j) {
            result.push_back(matrix[top][j]);
        }
        ++top; // Move the top boundary down

        // Traverse from top to bottom along the right column
        for (int i = top; i <= bottom; ++i) {
            result.push_back(matrix[i][right]);
        }
        --right; // Move the right boundary left

        if (top <= bottom) {
            // Traverse from right to left along the bottom row
            for (int j = right; j >= left; --j) {
                result.push_back(matrix[bottom][j]);
            }
            --bottom; // Move the bottom boundary up
        }

        if (left <= right) {
            // Traverse from bottom to top along the left column
            for (int i = bottom; i >= top; --i) {
                result.push_back(matrix[i][left]);
            }
            ++left; // Move the left boundary right
        }
    }

    return result;
}

复杂度分析

  • 时间复杂度: $O(m \times n)$ 每个元素被访问一次，总共 $m \times n$ 个元素。
  • 空间复杂度: $O(1)$ 除了存储结果的数组 result，没有使用额外的空间。

示例运行

输入:

1
2

vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vector<int> result = spiralOrder(matrix);

输出:

1

// result = {1, 2, 3, 6, 9, 8, 7, 4, 5};

边界情况

  • 如果矩阵为空：返回空数组。
  • 如果矩阵为单行或单列：直接按行或列顺序返回。
  • 如果矩阵为 $1 \times 1$：返回该元素。

48. 旋转图像

问题描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

1
2

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

1
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].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

题解

以下是针对问题 48 的 C++ 解法，采用原地旋转的方法。

解题思路

要将一个矩阵顺时针旋转 90 度，可以分两步完成：

  1. 先沿主对角线翻转（左上到右下的对角线），使得行列元素交换。
  2. 再沿垂直中线翻转，将每一行的元素顺序颠倒。

通过这两步操作，我们可以在不使用额外空间的情况下实现矩阵的顺时针旋转。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
using namespace std;

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();

    // Step 1: Transpose the matrix (swap along the main diagonal)
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }

    // Step 2: Reverse each row (flip along the vertical centerline)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n / 2; ++j) {
            swap(matrix[i][j], matrix[i][n - j - 1]);
        }
    }
}

复杂度分析

  • 时间复杂度:

    $O(n^2)$

    • 转置矩阵需要遍历矩阵上三角部分，共 $\frac{n(n-1)}{2}$ 次操作。
    • 翻转每行需要 $n/2$ 次操作，总共 $n^2 / 2$ 次操作。
    • 总体复杂度是 $O(n^2)$。

  • 空间复杂度:

    $O(1)$

    • 只使用了常量级别的辅助变量。

示例运行

输入:

1
2

vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
rotate(matrix);

输出:

1

// matrix = {{7, 4, 1}, {8, 5, 2}, {9, 6, 3}};

边界情况

  1. 矩阵为 $1 \times 1$：旋转后矩阵不变。
  2. 矩阵为 $2 \times 2$：最小的可旋转矩阵，仍然满足算法要求。
  3. 负数或较大数值的矩阵：不会影响算法的正确性。

补充说明

这个解法充分利用了二维矩阵的对称性质，通过两次原地翻转实现了旋转操作，非常高效且简洁。

240. 搜索二维矩阵 II

问题描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
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 = 5
输出：true

示例 2：

img

1
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.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • $-10^9 <= matrix[i][j] <= 10^9$
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • $-10^9 <= target <= 10^9$

题解

以下是针对问题 240 的高效 C++ 解法，利用矩阵的排序特性实现：

解题思路

我们可以从矩阵的 右上角 开始搜索：

  1. 比较当前位置的元素和目标值：
    • 如果当前位置的元素等于目标值，返回 true。
    • 如果当前位置的元素大于目标值，则当前列的所有元素都大于目标值，向左移动一列。
    • 如果当前位置的元素小于目标值，则当前行的所有元素都小于目标值，向下移动一行。
  2. 重复以上过程，直到超出矩阵边界。

这种方法可以高效缩小搜索范围，每次移动时排除一整行或一整列。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) {
        return false;
    }

    int m = matrix.size();
    int n = matrix[0].size();
    int row = 0, col = n - 1; // 从右上角开始

    while (row < m && col >= 0) {
        if (matrix[row][col] == target) {
            return true; // 找到目标值
        } else if (matrix[row][col] > target) {
            --col; // 左移一列
        } else {
            ++row; // 下移一行
        }
    }

    return false; // 未找到目标值
}

复杂度分析

  • 时间复杂度: $O(m + n)$ 每次移动时，要么减少一列（向左移动），要么减少一行（向下移动）。最多移动 $m + n$ 次。
  • 空间复杂度: $O(1)$ 只使用了常量空间，没有额外的数据结构。

示例运行

输入:

1
2
3
4
5
6
7
8
9

vector<vector<int>> 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}
};
int target = 5;
bool result = searchMatrix(matrix, target);

输出:

1

// result = true;

边界情况

  1. 空矩阵：返回 false。
  2. 矩阵只有一行或一列：仍然适用于该算法。
  3. 目标值超出矩阵范围：如 target = -1 或 target = 31，快速返回 false。

扩展

  • 如果需要查找多个目标值，可以对每个目标值分别调用该函数，或根据具体问题需求调整算法。
leetcode, hot100
C++ leetcode 矩阵
本文由作者按照 CC BY 4.0 进行授权