关于前端:美团二面算法题沿对角线遍历二维数组

47次阅读

共计 1134 个字符，预计需要花费 3 分钟才能阅读完成。

美团二面的时候面试官出了这道题，一起来看下：

实现一个函数，沿对角线遍历二维数组

例如：
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
打印输出：
[3, 2, 6, 1, 5, 9, 4, 8, 7]

之前没碰到过对角线遍历的，只做过 Leetcode 48 旋转图像这样找法则的题。过后没想进去，只写了个伪代码大抵说了下思路（还望面试官手下留情 😅）。昨天在解 N 皇后 问题的时候，须要遍历二维数组对角线上的元素，这道题忽然来了思路，上面把解题思路跟大家分享下。

这道题的外围就是要实现一个函数 diagonalTraverse，给定某个元素坐标，而后沿着右下角的方向进行遍历。例如给定的元素是 2，那就按 2 -> 6 的程序进行遍历；给定的元素是 1，按 1 -> 5 -> 9 的程序遍历。

右下角方向遍历其实很简略，每次给以后元素的横坐标和纵坐标别离 + 1，就能够实现了，diagonalTraverse 函数的实现如下：

public List<Integer> diagonalTraverse(int x, int y, int n, int m) {List<Integer> list = new ArrayList<>();
    while (x <= n && y <= m) {list.add(arr[x][y]);
        x++;
        y++;
    }
    return list;
}

x 和 y 示意以后元素的坐标，n 和 m 别离代表 arr.length-1 和 arr[0].length-1
在遍历的时候要留神不能越界

有了这个函数之后，咱们只有依照下图从右到左，从上到下的程序给它传入边界元素坐标，就能够实现题目要求的对角线遍历的成果了。

从上图能够看进去，传入坐标的时候分两次比拟好解决，第一次遍历程度方向（3 -> 2 -> 1），第二次遍历垂直方向（4 -> 7）。flatArray 函数的实现如下：

public List<Integer> flatArray(int[][] matrix) {
    this.arr = matrix;
    final int n = arr.length - 1;
    final int m = arr[0].length - 1;
    List<Integer> res = new ArrayList<>(); // 保留遍历后果
    
    for (int i=m; i>=0; i--) {
        // 遍历程度方向
        List<Integer> list = diagonalTraverse(0, i, n, m);
        res.addAll(list);
    }
    
    for (int i=1; i<=n; i++) {
        // 遍历垂直方向
        List<Integer> list = diagonalTraverse(i, 0, n, m);
        res.addAll(list);
    }
    
    return res;
}

明天的文章就到这里，残缺代码能够看我的 GitHub：