2025/5/27大约 5 分钟
矩阵
Leetcode Hot100第五个小专题，四道题，矩阵不要想得太复杂，就是一个二维数组。
矩阵置零
力扣题目连接：矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,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]]class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();//获取行数和列数
vector<int> mSig(m,0); //定义行标记，当矩阵中某个元素为零时，标记其所在行
vector<int> nSig(n,0);//定义列标记，当矩阵中某个元素为零时，标记其所在列
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(matrix[i][j]==0){
mSig[i]=1;
nSig[j]=1;
}
}
}
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(mSig[i]==1||nSig[j]==1){
matrix[i][j] = 0;
}
}
}
}
};螺旋矩阵
力扣题目连接：螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 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]//可以模拟遍历路径
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
if(matrix.size()==0||matrix[0].size()==0){
return {};
}
int mBegin = 0,mEnd = matrix[0].size()-1,nBegin = 0,nEnd = matrix.size()-1;//四个值分别是每一行的开始位置，每一行的结束位置，每一列的开始位置，每一列的结束位置
while(true){
for(int i = mBegin;i<=mEnd;i++){ //第一行从左向右遍历，加入到结果数组中
result.push_back(matrix[nBegin][i]);
}
if(++nBegin>nEnd) break;//紧接着要检查一下列的起始位置，注意这里是++nBegin，也就是先自增再检查
for(int i = nBegin;i<=nEnd;i++){//从mEnd所在列开始从上往下遍历，加入到结果中
result.push_back(matrix[i][mEnd]);
}
if(--mEnd<mBegin) break;//以下同理，模拟遍历路径并作判断，可以自己根据代码走一遍示例一
for(int i = mEnd;i>=mBegin;i--){
result.push_back(matrix[nEnd][i]);
}
if(--nEnd<nBegin) break;
for(int i=nEnd;i>=nBegin;i--){
result.push_back(matrix[i][mBegin]);
}
if(++mBegin>mEnd) break;
}
return result;
}
};旋转图像
力扣题目连接：螺旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 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]]思路一：第一眼看到这个题，可能又会想到去模拟矩阵的旋转行为，思考每个节点会旋转到哪里，这种方法应该是可行的，但是我们可以稍微观察一下，就会发现，第一列变成了第一行，第二列变成了第二行，以此类推，并且每一行的第一个数变成了当时该列的最后一个数（即每一列做了个倒叙变成了行），那么这样就简单了，可以用一个二维数组（矩阵）暂储，再做原地变换就行了，空间可能占用较多，待会思考如何优化
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
vector<vector<int>> result;
vector<int> current;
for(int i = 0;i<matrix[0].size();i++){ //这里其实不用[0]因为n*n嘛，所以行和列的长度是一样的
for(int j=matrix.size()-1;j>=0;j--){
current.push_back(matrix[j][i]);
}
result.push_back(current);
current.clear();
}
matrix=result;
}
};思路二：上面那个方法可能太简单了，面试的时候大概率不会让你用那个方法，还有第二种方法，找出相关的对应位置，做一个旋转，这就需要暂存第一个值，直接看官方思路吧。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0;i<n/2;i++){
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;
}
}
}
};搜索二维矩阵 II
力扣题目连接：搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：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：
输入：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思路一：最简单的思路就是暴力，遍历所有元素。
思路二：在思路一的基础上可以做一个优化，每一行都进行一个二分查找，降低时间复杂度
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(auto &row:matrix){//注意这里要用引用，而不能直接用值拷贝(auto row:matrix)，因为我们没有做数值更改不会影响原矩阵，并且如果某一行数值很多，使用拷贝可能会超内存
auto it = lower_bound(row.begin(),row.end(),target);
if(it!=row.end()&&*it==target){
return true;
}
}
return false;
}
};