『LeetCode』498 对角线遍历

题目

498. 对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

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

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

提示：

m == mat.length
n == mat[i].length
\(1 <= m, n <= 10^{4}\)
\(1 <= m * n <= 10^{4}\)
\(-10^{5} <= mat[i][j] <= 10^{5}\)

题解

【对角线遍历】简单模拟

模拟

通过观察可以发现，除了在边界上以外，只有两个方向，分别是左下向右上，右上向左下，每遇到边界就换个方向即可。

比较棘手的是边界的处理，分四种情况讨论即可，具体来说：

右边界：向下走，转弯
下边界：向右走，转弯
左边界：向下走，转弯
上边界：向右走，转弯

注意到：处理边界情况的顺序很重要，右边界和下边界的处理必须优先于上边界和左边界，因此虽然左右和上下这两组的处理方法相同但不能合并在一起。

# Code language: Python
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        dir = ((-1, 1), (1, -1))
        n, m = len(mat), len(mat[0])
        d, x, y = 0, 0, 0
        ans = list()
        while x < n and y < m:
            ans.append(mat[x][y])
            dx, dy = dir[d]
            if y + dy == m:
                x += 1
                d = 1 - d
            elif x + dx == n:
                y += 1
                d = 1 - d
            elif y + dy == -1:
                x += 1
                d = 1 - d
            elif x + dx == -1:
                y += 1
                d = 1 - d
            else:
                x += dx
                y += dy
        return ans

// Code language: Java
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int[][] dir = new int[][] {{-1, 1}, {1, -1}};
        int n = mat.length, m = mat[0].length;
        int[] ans = new int[n * m];
        for (int d = 0, x = 0, y = 0, i = 0; x < n && y < m; ) {
            ans[i++] = mat[x][y];
            int dx = dir[d][0], dy = dir[d][1];
            if (y + dy == m) x++;
            else if (x + dx == n) y++;
            else if (y + dy == -1) x++;
            else if (x + dx == -1) y++;
            else {
                x += dx; y += dy;
                continue;
            }
            d = 1 - d;
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<vector<int>> dir{{-1, 1}, {1, -1}};
        vector<int> ans;
        for (int d = 0, x = 0, y = 0, n = mat.size(), m = mat[0].size(); x < n && y < m; ) {
            ans.emplace_back(mat[x][y]);
            int dx = dir[d][0], dy = dir[d][1];
            if (y + dy == m) x++;
            else if (x + dx == n) y++;
            else if (y + dy == -1) x++;
            else if (x + dx == -1) y++;
            else {
                x += dx; y += dy;
                continue;
            }
            d = 1 - d;
        }
        return ans;
    }
};

时间复杂度: \(O(nm)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』498 对角线遍历

题目

标签

题解

模拟