力扣热题100——矩阵

矩阵置零

采用定义两个数组row[m],col[n]分别表示所有的行和列 然后遍历原矩阵 如果矩阵matrix[i][j] ==0时 就直接令row[i]= col[j]=0;
最后再遍历一次数组，如果row[i]或者col[j]为0则令该元素为0

class Solution{
public:void setZeros(vector<vector<int>>& matrix){int m = matrix.size();int n = matrix[0].size();vector<int> row(m),col(n);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!matrix[i][j]){row[i] = col[j] = 1;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(row[i]||col[j]){matrix[i][j] = 0;}}}}
};

螺旋矩阵

定义矩阵的上下左右边界，然后模拟矩阵的螺旋过程

class Solution{
public:vector<int> spiralOrder(vector<vector<int>>& matrix){if(matrix.size()==0||matrix[0].size()==0){return {};}int m = matrix.size();int n = matrix[0].size();int l=0,r=n-1,t=0,b=m-1;vector<int> ans;while(ans.size()<m*n){for(int i=l;i<=r;i++){ans.emplace_back(matrix[t][i]);}if(++t>b) break;for(int i=t;i<=b;i++){ans.emplace_back(matrix[i][r]);}if(--r<l) break;for(int i=r;i>=l;i--){ans.emplace_back(matrix[b][i]); }if(--b<t) break;for(int i=b;i>=t;i--){ans.emplace_back(matrix[i][l]);}if(++l>r) break;}return ans;}
};

旋转图像

这里介绍两种做法：
一个是观察翻转矩阵的规律
二是通过矩阵的上下翻转+对角线翻转

---

通过观察发现矩阵中第i行的第j个元素，在旋转后，他出现在倒数第i列的第j个位置

class Solution{
public:void rotate(vector<vector<int>>& matrix){int n = matrix.size();auto matrix_new = matrix;for(int i=0;i<n;i++){for(int j=0;j<n;j++){matrix_new[j][n-i-1] = matrix[i][j];}}//这里也是值拷贝matrix = matrix_new;}
}

第二种方法是用翻转代替旋转
通过上下翻转可以得到：matrix[row][col] -> matrix[n-row-1][col]
再通过主对角线翻转可以得到：matrix[row][col]->marix[col][row]
最后将两者联立即可得到：
matrix[col][n-row-1] = matrix[row][col]

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;j++){swap(matrix[i][j],matrix[n-i-1][j]);}}//主对角线线翻转for(int i=0;i<n;i++){for(int j=0;j<i;j++){swap(matrix[i][j],matrix[j][i]);}}}
};

搜索二维矩阵 II

这里介绍两种做法：
1.对矩阵进行遍历查找，从[0][0]开始，并且判断如果下一个数（按列）大于了target就break；按行也可判断如果下一行的第一个元素如果大于target，也直接break。
2.对每一行使用一次二分查找，判断target是否在该行

class Solution{
public:bool searchMatrix(vector<vector<int>>& matrix,int target){int m = matrix.size();int n = matrix[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(matrix[i][j]==target) return true;if(matrix[i][j+1]>target&&(j+1)<n) break;}if(matrix[i+1][0]>target&&(i+1)<m) break;}return false;}
}

---

方法二

class Solution{
public:bool searchMatrix(vector<vector<int>>& matrix,int target){for(const auto& row:matrix){auto it = lower_bound(row.begin(),row.end(),target);if(it!=row.end() && *it==target){return true;}}return false;}
}