对角线遍历

作者: BroQiang

发布于 2019-05-13 | 最后更新 2019-05-13


题目来自: https://leetcode-cn.com/problems/diagonal-traverse/

原题

描述

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

示例

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

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

解释:

diagonal_traverse

说明

给定矩阵中的元素总数不会超过 100000 。

分析

这个题目的题意很容易理解,就是将每个坐标点的 nums[x][y] 对应的值放到一个数组中,先向右上移动, 当达到边界的时候再向左下移动,达到边界的之后再向右上移动 …… ,一直到所有的元素遍历一遍。

先假设下面几个变量,后面解释的时候容易理解一些:

  • row 一维数组的长度, 也就是对应图中的总行数

  • col 二维数组的长度, 也就是对应图中的总列数

  • x 一维数组的索引,也就是代表当前坐标是第几行

  • y 二维数组的索引,也就是代表当前坐标是第几列

向右上移动的时候会有下面几种情况:

  • 坐标在第 1 行( x=0 )时,例如中 1 的右上位置, 不能再向上移动, 因为上面已经倒了顶部, 再移动就越界了, 所以只能向右移动一步(y+1), 并且下一次就要开始向左下移动了。

  • 坐标在最后一列,如图中 3 的位置,此时就不能再向右上移动了,要向下移动一步(x 不变, y = col-1), 并且下一次开始就要向左下移动了。

  • 剩下的情况, 就正常向右上移动 x–, y++ 即可。

向左下移动时候的几种情况:

这个其实和右上差不多,就是更换下 x, y 的坐标。

  • 坐标在第 1 列( y=0 )时,例如图中 4 的位置,这时不能再向左移动,需要向下移动一步,并且下 一次就要改变方向向右上移动了, y =0, x + 1 。

  • 坐标在最后一行, 如图中 8 的位置,此时就不能再向下移动(越界),要右移一步,并且下次移动转变 方向, y 不变, x = row -1 。

  • 剩下的就正常向左下移动 x+1, y-1 即可。

解法 1

上面说明如果看懂,这个就很简单了,也是我上来开始想到的思路。 就是按照顺序去 ++ -- 坐标即可, 注意每种移动对应的两个越界点即可,详细见代码中的注释:

func findDiagonalOrder(matrix [][]int) []int {
    // 矩阵的行和列
    row := len(matrix)
    if row == 0 {
        return nil
    }

    col := len(matrix[0])
    // 矩阵的横纵坐标,用来记录一维数组和二维数组对应的 key
    x, y := 0, 0
    // 标记是右上方向还是左下方向, 右上开始
    flag := true

    // 初始化记录结果的 slice, 容量是矩阵中坐标的数量
    res := make([]int, row*col)

    for i:=0; i < row*col; i++ {
        // 根据获得的 x, y 将数据添加
        res[i] = matrix[x][y]

        // 计算移动后的坐标,下次添加的时候使用

        // 右上移动 x-- , y++
        if flag {
            x--
            y++
            // 如果没有出界,就继续下一次
            if 0 <= x && y < col {
                continue
            }

            // 只要越界,就要开始相反的方向移动
            flag = false

            // 右上移动时,x < 0 , y 没有越界,
            // 比如对应图中数字 1, 2 的上方位置, 此时的坐标是 -1, 1
            if x < 0 && y < col {
                x = 0
                continue
            }

            // 如果不是上面的越界方式,就是 x, y 都出界了,
            // 比如图中 3 右上的位置, 此时 x, y = -1, 3 ,因为第一排已经遍历完成,
            // 需要移动到下一行再开始,所以要 -1+2 , y 就是它的最大长度的坐标即可
            x = x+2
            y = col-1

            continue
        }

        // 如果是向左下移动
        x++
        y--

        // 如果没有越界,就继续下一次
        if 0 <= y && x < row {
            continue
        }

        // 只要有越界就该翻转方向了
        flag = true

        // 如果 y 越界, x 没有越界,就像图中 4 左下的位置,此时是 x, y = 2, -1
        if y < 0 && x < row {
            y = 0
            continue
        }

        // y 越界了, 就像图中 8 的左下,需要将坐标移动到 9 的位置
        y = y + 2
        x = row-1
    }

    return res
}

解法 2

这个和上一个思路是完全一致的,就是修改了下写法,提交后执行时间和内存消耗都有了些许提高。

func findDiagonalOrder(matrix [][]int) []int {
    row := len(matrix)
    if row == 0 {
        return nil
    }

    col := len(matrix[0])
    x, y := 0, 0
    flag := true

    res := make([]int, row*col)

    for i:=0; i < row*col; i++ {
        res[i] = matrix[x][y]
        if flag {
            if y == col -1 {
                x++
                flag = false
            } else if x== 0 {
                y++
                flag = false
            } else {
                x--
                y++
            }
        } else {
            if x == row -1 {
                y++
                flag = true
            } else if y == 0 {
                x++
                flag = true
            } else {
                x++
                y--
            }
        }
    }

    return res
}

解法 3

观察对角线索引 x+y 的和,会发现,向右上移动的时候的 x+y 为偶数, 向左下移动的时候 x+y 为奇数, 其他的就和上面的解法 2 思路是一致的。

func findDiagonalOrder(matrix [][]int) []int {
    row := len(matrix)
    if row == 0 {
        return nil
    }

    col := len(matrix[0])
    x, y := 0, 0

    res := make([]int, row*col)

    for i:=0; i < row*col; i++ {
        res[i] = matrix[x][y]

        // 偶数,向右上
        if (x+y) %2 == 0 {
            if y == col -1 {
                x++
            } else if x == 0 {
                y++
            } else {
                x--
                y++
            }
        } else {
            if x == row -1 {
                y++
            } else if y == 0 {
                x++
            } else {
                x++
                y--
            }
        }
    }

    return res
}