上海网站建设关键词排名,邯郸铸邯网络信息科技有限公,小饭店普通装修,低俗网站推广哪里找73. 矩阵置零
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
法一#xff1a;
var setZeroes function(matrix) {let setX new Set(); // 用于存储需要置零的行索引let setY new Set(); //…73. 矩阵置零
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
法一
var setZeroes function(matrix) {let setX new Set(); // 用于存储需要置零的行索引let setY new Set(); // 用于存储需要置零的列索引let row matrix.length;let col matrix[0].length;for(let i0;irow;i){for(let j0;jcol;j){if(matrix[i][j]0){setX.add(i);setY.add(j);}}}// 将需要置零的行全置为 0for(let i of setX){for(let j0;jcol;j){matrix[i][j]0;}}// 将需要置零的列全置为 0for(let i of setY){for(let j0;jrow;j){matrix[j][i]0;}}
};时间复杂度O(m*n)空间复杂度O(mn)额外使用了两个set来存储行和列索引
法二
解题思路
使用矩阵的第一行和第一列作为标记区域 用第一行标记需要置零的列。用第一列标记需要置零的行。 步骤概述 第一步先遍历整个矩阵记录哪些行和列需要置零但不要急着修改矩阵。 使用第一行的元素记录某一列是否需要置零。使用第一列的元素记录某一行是否需要置零。此外需要一个变量标记第一行和第一列本身是否需要置零。 第二步根据第一行和第一列的标记修改矩阵对应的行和列为零。第三步单独处理第一行和第一列因为它们被用作标记最后再更新。
var setZeroes function(matrix) {let row matrix.length;let col matrix[0].length;// 标记第一列和第一行是否需要置零let firstRowZero false;let firstColZero false;for (let i 0; i row; i) { // 检查第一列是否需要置零if (matrix[i][0] 0) {firstColZero true;break;}}for (let j 0; j col; j) { // 检查第一行是否需要置零if (matrix[0][j] 0) {firstRowZero true;break;}}for (let i 1; i row; i) { // 使用第一行和第一列标记需要置零的行和列for (let j 1; j col; j) {if (matrix[i][j] 0) {matrix[i][0] 0; // 标记该行需要置零matrix[0][j] 0; // 标记该列需要置零}}}for (let i 1; i row; i) { // 遍历矩阵根据标记置零跳过第一行和第一列for (let j 1; j col; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}if (firstColZero) { // 根据标记处理第一列for (let i 0; i row; i) {matrix[i][0] 0;}}if (firstRowZero) { // 根据标记处理第一行for (let j 0; j col; j) {matrix[0][j] 0;}}
};
时间复杂度O(m*n)空间复杂度O(1)
54 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
思路
定义边界使用四个变量 top、bottom、left、right 分别表示矩阵的上、下、左、右边界。遍历顺序按照顺时针方向依次遍历上边界、右边界、下边界和左边界。调整边界每遍历完一个边界后调整相应的边界。重复遍历直到所有元素都被遍历。
代码实现
var spiralOrder function(matrix) {let res [];// 维护四个边界let left 0;let right matrix[0].length-1;let top 0;let bottom matrix.length-1;// 遍历while(leftrighttopbottom){for(let ileft;iright;i){ // 遍历上边界res.push(matrix[top][i]);}top;for(let itop;ibottom;i){ // 遍历右边界res.push(matrix[i][right]);}right--;if(topbottom){for(let iright;ileft;i--){ // 遍历下边界res.push(matrix[bottom][i]);}bottom--;}if(leftright){for(let ibottom;itop;i--){ // 遍历左边界res.push(matrix[i][left]);}left;}}return res;
};48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
思路
转置矩阵将矩阵的行和列互换即 matrix[i][j] 和 matrix[j][i] 交换。翻转每一行将转置后的矩阵的每一行反转。
代码实现
var rotate function(matrix) {for(let i0;imatrix.length;i){for(let ji;jmatrix.length;j){[matrix[i][j],matrix[j][i]] [matrix[j][i],matrix[i][j]];}}for(let i0;imatrix.length;i){matrix[i].reverse();}
};240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
思路从右上角或左下角开始搜索 从右上角开始 初始化指针在矩阵的右上角即 row 0col n - 1。如果当前元素等于 target返回 true。如果当前元素大于 target说明目标值不可能在当前列因此向左移动一列col–。如果当前元素小于 target说明目标值不可能在当前行因此向下移动一行row。重复上述步骤直到找到目标值或指针越界。 从左下角开始 初始化指针在矩阵的左下角即 row m - 1col 0。如果当前元素等于 target返回 true。如果当前元素大于 target说明目标值不可能在当前行因此向上移动一行row–。如果当前元素小于 target说明目标值不可能在当前列因此向右移动一列col。重复上述步骤直到找到目标值或指针越界。
代码实现从右上角开始
var searchMatrix function(matrix, target) {if (matrix.length 0 || matrix[0].length 0) return false;let row 0;let col matrix[0].length-1;while(rowmatrix.length col0){if(matrix[row][col]target){return true;}else if(matrix[row][col]target){col--;}else{row;}}return false;
};
