爱站网长尾词挖掘,全国首批9所重点马院网站建设,网站建设公司豆瓣,关键词排名工具有哪些1.矩阵置0 思路分析#xff1a;使用标记数组
记录需要置为 0 的行和列#xff1a;使用两个布尔数组 zeroRows 和 zeroCols 来记录需要置为 0 的行和列两次遍历 第一遍遍历整个矩阵#xff0c;找到所有为0的元素#xff0c;并更新zeroRows和zeroCols#xff1b;第二遍遍历…1.矩阵置0 思路分析使用标记数组
记录需要置为 0 的行和列使用两个布尔数组 zeroRows 和 zeroCols 来记录需要置为 0 的行和列两次遍历 第一遍遍历整个矩阵找到所有为0的元素并更新zeroRows和zeroCols第二遍遍历依照zeroRows和zeroCols的状态将对应的行和列元素置为0时间复杂度为 O(m * n)空间复杂度为 O(m n)其中 m 和 n 分别是矩阵的行数和列数。
具体实现代码详解版
class Solution {
public:void setZeroes(vectorvectorint matrix) {if (matrix.empty()) return;int rows matrix.size();int cols matrix[0].size();vectorbool zeroRows(rows,false);vectorbool zeroCols(cols,false);//第一次遍历记录哪些行和列需要置为0for(int i 0 ; i rows ; i ){for(int j 0 ; j cols ;j ){if(matrix[i][j] 0 ){zeroRows[i] true;//记录第i行需要置为0zeroCols[j] true;//记录第j列需要置为0}}}//第二次遍历根据记录的行和列将其置为0for(int i 0 ; i rows ; i ){for(int j 0 ; j cols ;j ){if(zeroRows[i] || zeroCols[j] ){matrix[i][j] 0;}}}}
};2.螺旋矩阵 思路分析要以顺时针螺旋顺序返回一个矩阵中的所有元素可以采用四个边界上、下、左、右来控制遍历的范围。具体步骤如下
初始化边界设定四个变量top,bottom,leftright分别表示当前未遍历部分的上下左右边界循环遍历 从左到右遍历当前的top行更新top边界从上到下遍历当前的right列更新right边界检查是否仍有行可遍历若有从右到左遍历当前的bottom行更新bottom边界检查是否仍有列可遍历若有从下到上遍历当前的left列更新left边界 重复以上步骤直到所有元素被遍历
具体实现代码详解版
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {vectorint 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){//从左到右遍历上边界for(int j left ; j right ; j ){result.push_back(matrix[top][j]);}top ;//下移//从上到下遍历右边界for(int i top ; i bottom ; i ){result.push_back(matrix[i][right]);}right --;//左移if(top bottom){//检查是否仍有行可遍历//从右到左遍历下边界for(int j right ; j left ; j --){result.push_back(matrix[bottom][j]);}bottom --;//上移}if(left right){//从下到上遍历左边界for(int i bottom ; i top ; i --){result.push_back(matrix[i][left]);}left ;//右移}}return result;}
};还有一种写法供参考
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {vector int ans;if(matrix.empty()) return ans; //若数组为空直接返回答案int u 0; //赋值上下左右边界int d matrix.size() - 1;int l 0;int r matrix[0].size() - 1;while(true){for(int i l; i r; i) ans.push_back(matrix[u][i]); //向右移动直到最右if( u d) break; //重新设定上边界若上边界大于下边界则遍历遍历完成下同for(int i u; i d; i) ans.push_back(matrix[i][r]); //向下if(-- r l) break; //重新设定右边界for(int i r; i l; --i) ans.push_back(matrix[d][i]); //向左if(-- d u) break; //重新设定下边界for(int i d; i u; --i) ans.push_back(matrix[i][l]); //向上if( l r) break; //重新设定左边界}return ans;}
};3.旋转图像 思路分析要在原地顺时针旋转 n×n 的矩阵可以分为两个步骤先进行矩阵的转置然后再对每一行进行反转。
转置通过双重循环将 matrix[i][j] 和 matrix[j][i] 进行交换从而完成转置操作。注意这里只需遍历上三角矩阵以避免重复交换反转每一行std::reverse 函数反转每一行完成最终的旋转。
具体实现代码详解版
void rotate(vectorvectorint matrix) {int n matrix.size();// 1. 转置矩阵for (int i 0; i n; i) {for (int j i 1; j n; j) {swap(matrix[i][j], matrix[j][i]);}}// 2. 反转每一行for (int i 0; i n; i) {reverse(matrix[i].begin(), matrix[i].end());}
}
4.搜索二维矩阵II 思路分析使用一种从矩阵的右上角开始的搜索方法这种方法的时间复杂度为 O(mn)其中 m 是矩阵的行数n 是列数。
从右上角开始设置 row 为 0col 为最后一列的索引。搜索逻辑 如果当前元素等于目标值则返回 true如果当前元素等大于目标值说明target在左侧向左移动减少列索引如果当前元素等小于目标值说明target在下侧向下移动增加行索引
具体实现代码详解版):
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {// 检查矩阵是否为空if (matrix.empty() || matrix[0].empty()) return false;int m matrix.size(); // 矩阵行数int n matrix[0].size(); // 矩阵列数int row 0; // 从第一行开始int 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; // 未找到目标值}
};
