矩阵¶
约 853 个字 244 行代码 1 张图片 预计阅读时间 7 分钟
矩阵置零¶
题目描述：
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。
示例：
Text Only
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
输入：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
算法解析：
这道题使用 原地算法 来节省空间：
-
核心思想 ：利用矩阵的第一行和第一列来记录需要置零的行和列
-
算法步骤 ：
-
遍历矩阵，找到所有0元素
-
将0元素所在行的第一个元素和所在列的第一个元素设为0
-
再次遍历矩阵，根据第一行和第一列的标记置零
- 具体实现 ：
-
使用flag_col0标记第一列是否需要置零
-
从第二列开始遍历，将0元素的行首和列首标记为0
-
从下往上、从右往左遍历，根据标记置零
-
时间复杂度 ：O(mn) - 需要遍历矩阵两次
-
空间复杂度 ：O(1) - 只使用常数额外空间
C++
#define itn int
#define nit int
#define nti int
#define tin int
#define tni int
#define retrun return
#define reutrn return
#define rutren return
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
class Solution
{
public:
void setZeroes(vector<vector<int>> &matrix)
{
bool flag_col0 = false;
for (int i = 0; i < matrix.size(); i++)
{
// 任意一行起始列为 0 标记为 true，最后这一列和 i 行会为 0
if (!matrix[i][0])
flag_col0 = true;
for (int j = 1; j < matrix[0].size(); j++)
if (!matrix[i][j])
matrix[i][0] = matrix[0][j] = 0;
}
for (int i = matrix.size() - 1; i >= 0; i--)
{
for (int j = 1; j < matrix[0].size(); j++)
if (!matrix[i][0] || !matrix[0][j])
matrix[i][j] = 0;
if (flag_col0)
matrix[i][0] = 0;
}
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 构造测试用例：matrix = [[1,1,1],[1,0,1],[1,1,1]]
vector<vector<int>> matrix = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
cout << "原始矩阵：" << endl;
for (const auto &row : matrix) {
for (int val : row)
cout << val << ' ';
cout << endl;
}
Solution().setZeroes(matrix);
cout << "置零后的矩阵：" << endl;
for (const auto &row : matrix) {
for (int val : row)
cout << val << ' ';
cout << endl;
}
return 0;
}
螺旋矩阵¶
题目描述：
给你一个 m x n 的矩阵，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例：
Text Only
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
输入：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
算法解析：
这道题使用 模拟法 按照螺旋路径遍历矩阵：
-
核心思想 ：模拟螺旋遍历的过程，按照右、下、左、上的顺序移动
-
算法步骤 ：
-
定义四个方向：右(0,1)、下(1,0)、左(0,-1)、上(-1,0)
-
按照螺旋顺序遍历矩阵
-
遇到边界或已访问元素时改变方向
- 具体实现 ：
-
使用dx、dy表示当前移动方向
-
访问当前位置后标记为已访问(-101)
-
检查下一个位置是否有效，无效则改变方向
-
时间复杂度 ：O(mn) - 需要访问矩阵中的每个元素
-
空间复杂度 ：O(1) - 只使用常数额外空间（不考虑输出数组）
C++
#define itn int
#define nit int
#define nti int
#define tin int
#define tni int
#define retrun return
#define reutrn return
#define rutren return
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
class Solution
{
public:
vector<int> spiralOrder(vector<vector<int>> &matrix)
{
vector<int> ans;
int n = matrix.size(), m = matrix[0].size(), size = n * m;
int i = 0, j = 0, dx = 0, dy = 1, tmp = 0;
while (size--)
{
ans.push_back(matrix[i][j]);
matrix[i][j] = -101;
if (i + dx < n && i + dx >= 0 && j + dy < m && j + dy >= 0 && matrix[i + dx][j + dy] != -101)
i += dx, j += dy;
else
tmp = dy, dy = -dx, dx = tmp, i += dx, j += dy;
}
return ans;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 构造测试用例：matrix = [[1,2,3],[4,5,6],[7,8,9]]
vector<vector<int>> matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
cout << "原始矩阵：" << endl;
for (const auto &row : matrix) {
for (int val : row)
cout << val << ' ';
cout << endl;
}
vector<int> res = Solution().spiralOrder(matrix);
cout << "螺旋遍历结果: ";
for (int val : res)
cout << val << ' ';
cout << endl;
return 0;
}
旋转图像¶
给定一个 n x n 的二维矩阵表示一个图像，请将图像顺时针旋转 90 度。必须原地旋转，不能使用额外空间。
C++
#define itn int
#define nit int
#define nti int
#define tin int
#define tni int
#define retrun return
#define reutrn return
#define rutren return
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
class Solution
{
public:
void rotate(vector<vector<int>> &matrix)
{
for (int i = 0; i < matrix[0].size(); i++)
for (int j = 0; j < matrix[0].size() - i; j++)
swap(matrix[i][j], matrix[matrix[0].size() - 1 - j][matrix[0].size() - 1 - i]);
for (int i = 0; i < matrix[0].size() / 2; i++)
for (int j = 0; j < matrix[0].size(); j++)
swap(matrix[i][j], matrix[matrix[0].size() - i - 1][j]);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (auto &row : matrix)
for (auto &val : row)
cin >> val;
Solution().rotate(matrix);
for (const auto &row : matrix) {
for (int val : row)
cout << val << ' ';
cout << '\n';
}
return 0;
}
搜索二维矩阵 II¶
给你一个满足下述属性的 m x n 整数矩阵：
- 每行的整数从左到右按升序排列
- 每列的整数从上到下按升序排列
给你一个整数 target，请你判断 target 是否存在于矩阵中。
C++
#define itn int
#define nit int
#define nti int
#define tin int
#define tni int
#define retrun return
#define reutrn return
#define rutren return
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
class Solution
{
public:
bool searchMatrix(vector<vector<int>> &matrix, int& target)
{
int x = 0, y = matrix[0].size() - 1;
while (x < matrix.size() && y >= 0)
{
if (matrix[x][y] == target)
return true;
if (matrix[x][y] > target)
--y;
else
++x;
}
return false;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m, n, target;
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
for (auto &row : matrix)
for (auto &val : row)
cin >> val;
cin >> target;
cout << (Solution().searchMatrix(matrix, target) ? "true" : "false") << '\n';
return 0;
}