二维矩阵转换（多种遍历方法）

2021-06-05 本文已影响0人 _code_x

1.螺旋矩阵（54-中）

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

示例：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

思路：直接模拟按层填充，定义左右上下边界，循环遍历矩阵。注意：如果是方阵，就可以直接退出循环，但是，如果存在l > r || t > b，则证明最后一次不是圈，是一行或者一列，这时我们可以直接终止循环。

代码：

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int m = matrix.length, n = matrix[0].length;
    int l = 0, r = n - 1, t = 0, b = m - 1;
    while (l <= r && t <= b) {
        for (int j = l; j <= r; ++j) {
            ans.add(matrix[t][j]);
        }
        t++;
        for (int i = t; i <= b; ++i) {
            ans.add(matrix[i][r]);
        }
        r--;
        if (l > r || t > b) {
            break;
        }
        for (int j = r; j >= l; --j) {
            ans.add(matrix[b][j]);
        }
        b--;
        for (int i = b; i >= t; --i) {
            ans.add(matrix[i][l]);
        }
        l++;
    }
    return ans;
}

2.螺旋矩阵II（59-中）

题目描述：生成1-n^2的所有元素，且元素按顺时针螺旋排列的正方形矩阵。

示例：

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路：与上题思路相同，区别是退出循环机制，采用num < tar，这样避免了判断奇偶的情况。

代码：

public int[][] generateMatrix(int n) {
    int l = 0, r = n - 1, t = 0, b = n - 1;
    int[][] matrix = new int[n][n];
    int num = 1;
    while (l <= r && t <= b) {
        for (int j = l; j <= r; ++j) {
            matrix[t][j] = num++;
        }
        t++;
        for (int i = t; i <= b; ++i) {
            matrix[i][r] = num++;
        }
        r--;
        for (int j = r; j >= l; --j) {
            matrix[b][j] = num++;
        }
        b--;
        for (int i = b; i >= t; --i) {
            matrix[i][l] = num++;
        }
        l++;
    }
    return matrix;
}

3.对角线打印矩阵（498-中）

题目描述：给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例：

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]

思路：两种方向的变更，右上到左下，依次交换方向，将结果加入数组。流程如下：

确定循环次数，即方向变更的次数 m + n - 1
从0开始，偶数次数为右上，奇数次数为右下（通过取余实现）
最后确定两个方向具体实现，比如右上方向，设横坐标x，纵坐标y，一般变化（x--, y++），但是注意边界处理，即上图中1 - 2, 3 - 6，对应不同的边界处理。左下方向类似。具体见代码

代码：

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int rowLength = mat.length;
        int colLength = mat[0].length;

        int[] ans = new int[rowLength * colLength];
        int loop = rowLength + colLength - 1;
        int x = 0;
        int y = 0;
        int index = 0;

        for (int i = 0; i < loop; i++) {
            if (i % 2 == 0) {
                while (x >= 0 && y < colLength) {
                    ans[index++] = mat[x][y];
                    x--;
                    y++;
                }
                if (y < colLength) {
                    // 对应1-2边界
                    x++;
                } else {
                    // 对应3-6边界，ps：需要将上一步while中的x和y位置进行修正(x加1, y不变)
                    x += 2; 
                    y--;
                }
            } else {
                while (x < rowLength && y >= 0) {
                    ans[index++] = mat[x][y];
                    x++;
                    y--;
                }
                if (x < rowLength) {
                    // 对应4-7边界
                    y++;

                } else {
                    // 对应8-9边界
                    x--;
                    y += 2;
                }
            }
        }
        return ans;
    }
}

4.旋转图像（48-中）

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

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

示例：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

思路：

法1：直接模拟旋转，可以看成一圈一圈的移动。注意：内层循环，为了避免奇数情况，每一圈可能有一个不移动，我们对n进行加1，可以自行举例n = 2 和 n = 3的情况。

法2：先水平翻转，然后主对角线翻转。

代码：

// 代码1
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 tmp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = tmp;
        }
    }
}

// 代码2
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 水平翻转
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];
            matrix[n - i - 1][j] = temp;
        }
    }
    // 主对角线翻转
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

5.搜索二维矩阵（74-中）

题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

思路：本题关键解题关键是矩阵有序，我们可以从右上角或者左下角出发，缩小数据搜索范围，遍历寻找目标值。

以右上角为例，当前遍历左边的元素比当前值小，当前遍历下边的元素比当前值大。

最优解为二分查找：本题中行尾和行首连接，也具有单调性，故可将二维矩阵转成一维矩阵去做。

代码：

// 直接搜索，时间复杂度：O(m + n)
public boolean searchMatrix(int[][] matrix, int target) {
    int i = 0, j = matrix[0].length - 1;
    while (i < matrix.length && j > -1) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) {
            j--;
        } else {
            i++;
        }
    }
    return false;
}

// 二分查找，时间复杂度：O(log(mn))
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int i = 0, j = m * n - 1;
    while (i < j) {
        int mid = i + ((j - i) >> 1);
        if (matrix[mid / n][mid % n] < target) {
            i = mid + 1;
        } else {
            j = mid;
        }
    }
    return matrix[i / n][i % n] == target;
}

6.搜索二维矩阵II（240-中）

题目描述：在有序矩阵中寻找指定数值。

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

示例：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路：直接搜索基本思路同上。但是二分查找则不同，上题我们首先在第一列小于目标值的第一个数，然后再查找目标行，但是由于本题数据排布整体不是严格单调的！

利用有序的性质，我们可以一行一行的进行二分查找（也可以一列一列的）

当某一行的第一个元素都大于target了，那么当前行和之后的行都不用考虑了
如果当前行的最后一个元素小于target，当前行排除，直接进入下一行。

代码：

// 直接搜索，时间复杂度：O(m + n)
public boolean searchMatrix(int[][] matrix, int target) {
    int i = 0, j = matrix[0].length - 1;
    while (i < matrix.length && j > -1) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) {
            j--;
        } else {
            i++;
        }
    }
    return false;
}

// 二分查找，时间复杂度：O(mlogn)
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] > target) {
            break;
        } 
        if (matrix[i][n - 1] < target) {
            continue;
        }
        int col = binarySearch(matrix[i], target);
        if (col != -1) {
            return true;
        }
    }
    return false;
}
// 二分查找目标值的索引(类似源码)
public int binarySearch(int[] arr, int target) {
    int i = 0, j = arr.length - 1;
    while (i <= j) {
        int mid = (i + j) >>> 1;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return -1;
}

7.矩阵置零（73-中）

题目描述：给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法（在函数输入矩阵上直接修改）。进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

示例：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

思路：本题的关键点：如果在输入矩阵上原地修改把行列修改成了 0，那么再遍历到 0 的时候就不知道是原本数组中的 0 还是我们修改得到的 0。所有的解法都是为了解决该问题。

方案1：遍历两遍矩阵，第一遍记录哪些行哪些列有0，第二遍置0。使用两个set进行记录，空间复杂度O(m + n)

方案2：核心：将第一行和第一列作为标志位，为了避免是由于第一行和第一列本来就有0造成的置0，我们需要对第一行第一列单独进行判断，只需要加两个boolean类型变量进行判断即可。

对于方案2优化，直接使用一个标志位，简化代码，但是不如两个标志位好理解。你可能会说一个不是造成了覆盖吗（原先第一个行某个位置不是0，现在是0）。

假设该列没有0，那么第一行对应位置一定不是0，如果是0，那么可能是本身，也可能是下边0导致修改，如何区别呢？正序置0我们没有办法区别，逆序置0即使是覆盖，那么该位置最终也一定是0。

代码：

// 空间复杂度：O(m + n)
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    Set<Integer> rowZero = new HashSet<>();
    Set<Integer> colZero = new HashSet<>();
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 0) {
                rowZero.add(i);
                colZero.add(j);
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (rowZero.contains(i) || colZero.contains(j)) {
                matrix[i][j] = 0;
            }
        }
    }
}

// 标记法，空间复杂度：O(1)
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean row0Flag = false;
    boolean col0Flag = false;
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            row0Flag = true;
            break;
        }
    }
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            col0Flag = true;
            break;
        }
    }
    // 第一行第一列作为标志位
    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;
            }
        }
    }
    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 (row0Flag) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }
    if (col0Flag) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

// 代码优化：一个标志
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean col0Flag = false;
     for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) col0Flag = true;
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 1; --j) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
        if (col0Flag) matrix[i][0] = 0;
    }
}