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 i=0;i<row;i++){for(let j=0;j<col;j++){if(matrix[i][j]===0){setX.add(i);setY.add(j);}}}// 將需要置零的行全置為 0for(let i of setX){for(let j=0;j<col;j++){matrix[i][j]=0;}}// 將需要置零的列全置為 0for(let i of setY){for(let j=0;j<row;j++){matrix[j][i]=0;}}
};

• 時間復雜度：O(m*n)
• 空間復雜度：O(m+n)，額外使用了兩個set來存儲行和列索引

法二：

解題思路：

1. 使用矩陣的第一行和第一列作為標記區域：
   • 用第一行標記需要置零的列。
   • 用第一列標記需要置零的行。
2. 步驟概述：
   • 第一步：先遍歷整個矩陣，記錄哪些行和列需要置零（但不要急著修改矩陣）。
     • 使用第一行的元素記錄某一列是否需要置零。
     • 使用第一列的元素記錄某一行是否需要置零。
     • 此外，需要一個變量標記第一行和第一列本身是否需要置零。
   • 第二步：根據第一行和第一列的標記，修改矩陣對應的行和列為零。
   • 第三步：單獨處理第一行和第一列（因為它們被用作標記，最后再更新）。

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 ，請按照 順時針螺旋順序 ，返回矩陣中的所有元素。

思路：

1. 定義邊界：使用四個變量 top、bottom、left、right 分別表示矩陣的上、下、左、右邊界。
2. 遍歷順序：按照順時針方向，依次遍歷上邊界、右邊界、下邊界和左邊界。
3. 調整邊界：每遍歷完一個邊界后，調整相應的邊界。
4. 重復遍歷：直到所有元素都被遍歷。

代碼實現：

var spiralOrder = function(matrix) {let res = [];// 維護四個邊界let left = 0;let right = matrix[0].length-1;let top = 0;let bottom = matrix.length-1;// 遍歷while(left<=right&&top<=bottom){for(let i=left;i<=right;i++){  // 遍歷上邊界res.push(matrix[top][i]);}top++;for(let i=top;i<=bottom;i++){  // 遍歷右邊界res.push(matrix[i][right]);}right--;if(top<=bottom){for(let i=right;i>=left;i--){  // 遍歷下邊界res.push(matrix[bottom][i]);}bottom--;}if(left<=right){for(let i=bottom;i>=top;i--){  // 遍歷左邊界res.push(matrix[i][left]);}left++;}}return res;
};

48. 旋轉圖像

給定一個 n × n 的二維矩陣 matrix 表示一個圖像。請你將圖像順時針旋轉 90 度。

你必須在原地旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。請不要 使用另一個矩陣來旋轉圖像。

思路：

1. 轉置矩陣：將矩陣的行和列互換（即 matrix[i][j] 和 matrix[j][i] 交換）。
2. 翻轉每一行：將轉置后的矩陣的每一行反轉。

代碼實現：

var rotate = function(matrix) {for(let i=0;i<matrix.length;i++){for(let j=i;j<matrix.length;j++){[matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]];}}for(let i=0;i<matrix.length;i++){matrix[i].reverse();}
};

240. 搜索二維矩陣 II

編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：

• 每行的元素從左到右升序排列。
• 每列的元素從上到下升序排列。
  

思路：從右上角或左下角開始搜索

1. 從右上角開始：

   • 初始化指針在矩陣的右上角（即 row = 0，col = n - 1）。
   • 如果當前元素等于 target，返回 true。
   • 如果當前元素大于 target，說明目標值不可能在當前列，因此向左移動一列（col–）。
   • 如果當前元素小于 target，說明目標值不可能在當前行，因此向下移動一行（row++）。
   • 重復上述步驟，直到找到目標值或指針越界。

2. 從左下角開始：

   • 初始化指針在矩陣的左下角（即 row = m - 1，col = 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(row<matrix.length && col>=0){if(matrix[row][col]===target){return true;}else if(matrix[row][col]>target){col--;}else{row++;}}return false;
};