73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

方法一

用两个标记数组分别记录每一行和每一列是否有零出现

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

方法二

用第一行和第一列来做标记数组，不使用额外空间，但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        //标记 
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        //设置0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。设定矩阵的 “左、上、右、下” 四个边界，模拟以上矩阵遍历顺序。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int left = 0, top = 0;
        int right = matrix[0].length - 1;
        int bottom = matrix.length - 1;
        int n = matrix.length * matrix[0].length;
        while (n > 0) {
            //从左到右
            for (int i = left; i <= right && n > 0; i++) {
                ans.add(matrix[top][i]);
                n--;    //每加一个n就减一
            }
            //第一行的结束了，所以top要加一
            top++;

            //从上到下
            for (int i = top; i <= bottom && n > 0; i++) {
                ans.add(matrix[i][right]);
                n--;
            }
            //最右边的一列结束了，所以right要减一
            right--;

            //从右到左
            for (int i = right; i >=left  && n > 0; i--) {
                ans.add(matrix[bottom][i]);
                n--;
            }
            //最下面的一行结束了，所以bottom要减一
            bottom--;

            //从下到上
            for (int i = bottom; i >= top && n > 0; i--) {
                ans.add(matrix[i][left]);
                n--;
            }
            //最左边的一列结束了，所以left要减一
            left++;
        }
        return ans;
    }
}

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像

方法一：使用额外的矩阵。

矩阵顺时针旋转 90º 后，可找到以下规律：

「第 i 行」元素旋转到「第 n−1−i列」元素；
「第 j 列」元素旋转到「第 j 行」元素；

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }
}

方法二：原地修改

矩阵旋转 90º 后，相当于依次先后执行 D→A, C→D , B→C , A→B，修改元素。由于第 1步 D→A 已经将 A覆盖导致 AAA 丢失，所以需要一个辅助变量存储一下A。

一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/41/41/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。

具体来看，当矩阵大小 n 为偶数时，取前 n/2行、前n/2列的元素为起始点；当矩阵大小 n 为奇数时，取前 n/2行、前 (n+1)/2列的元素为起始点。

「第 i 行」元素旋转到「第 n−1−i列」元素；
「第 j 列」元素旋转到「第 j 行」元素；

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        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 - 1 - j];
                matrix[n - i - 1][n - 1 - j] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m＊n矩阵 matrix 中的一个目标值target 。该矩阵具有以下特性：

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

方法一：暴力复杂度太高　O（ｍ＊ｎ）

方法二：每一行都进行二分查找

方法三：Z字型查找

二分查找每次搜索可以排除半行或半列的元素，Z字形查找每次搜索可以排除一行或一列的元素。

从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比：

当 matrix[i] [j]> target 时，执行 i– ，即消去第 i 行元素。
当 matrix[i] [j] < target 时，执行 j++ ，即消去第 j 列元素。
当 matrix[i] [j] == target 时，返回 true，代表找到目标值。
若行索引或列索引越界，则代表矩阵中无目标值，返回 false 。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) {
                i--;
            } else if (matrix[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }
}

Julian's Blog

力扣top100-矩阵

73. 矩阵置零

方法一

方法二

54. 螺旋矩阵

48. 旋转图像

240. 搜索二维矩阵 II