X

LEETCODE 1424. Diagonal Traverse II 解题思路分析

题目大意:

对角线遍历 II

给你一个列表 nums ,里面每一个元素都是一个整数列表。请你依照下面各图的规则,按顺序返回 nums 中对角线上的整数。

示例 1:

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

示例 2:

输入:nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
输出:[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

示例 3:

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

示例 4:

输入:nums = [[1,2,3,4,5,6]]
输出:[1,2,3,4,5,6]

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= nums[i][j] <= 10^9
  • nums 中最多有 10^5 个数字。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1424

解题思路分析:

这道题是一道矩阵题目,不过如果我们使用暴力解遍历每一条对角线的话,时间复杂度会达到O(n^2),由于矩阵的长和宽都是10的5次方数量级,这种算法显然会TLE。仔细观察本题,实际上它是一个不规则的矩阵,也就是说他每一行的长度是不同的,另外题目也给出数字的规模不会超过10的5次方,因此我们需要变换一个角度去思考问题。

首先我们应该将所有的数字进行分组,分组的标准即是他们是否在同一对角线上。判断同一对角线上的数字的方法很简单,即任意位置的横坐标加上纵坐标,值相同的所有点一定在同一对角线上。比如点(2,0),(1,1),(0,2)。

解题时,我们建立一个HashMap,来记录每条对角线的上所有点,key为对角线的id(横坐标加纵坐标),value为该对角线上所有的数字。另外我们要注意一下存储的顺序,由于每条对角线上的数字是从下向上(行数)排列的,因此我们从矩阵的最后一行开始遍历比较好。这样我们能够保证每条对角线上的数字已经按照顺序排列。对于当前行,我们再遍历它的每一列上的数字,使用当前行加上当前列的和,计算出当前数字所属的对角线id,将该数字存入map中对应该id的集合即可。重复此步骤直到循环结束。

另外,对角线的排列是从左至右,也就是他们id的升序排列。我们从0循环至最大id,分别取出map中该对应id的对角线上的所有数字,顺序将其放入返回结果即可。

实现代码:

public int[] findDiagonalOrder(List<List<Integer>> nums) {
    // 记录每条对角线上的数字
    Map<Integer, List<Integer>> map = new HashMap<>();
    // 最大对角线id
    int maxId=0;
    // 所有节点个数
    int size=0;
    // 从下向上循环每一行
    for(int i=nums.size()-1;i>=0;i--){
        // 取出当前行的所有数字
        List<Integer> list = nums.get(i);
        // 循环当前行的每一个数字
        for(int j=0;j<list.size();j++){
            // 当前数字所在对角线的id(行加列)
            int id = i+j;
            // 取得该对角线上的所有数字集合
            List<Integer> l = map.getOrDefault(id, new ArrayList<>());
            // 将当前数字加入集合
            l.add(list.get(j));
            // 将集合存入map
            map.put(id, l);
            // 更新最大对角线id
            maxId=Math.max(maxId, id);
            // 节点个数加一
            size++;
        }
    }
    // 初始化返回数组
    int[] res = new int[size];
    // 返回结果数组的当前下标
    int index=0;
    // 循环每一个对角线id
    for(int i=0;i<=maxId;i++){
        // 取得当前对角线上的所有数字
        List<Integer> l = map.get(i);
        // 将每个数字按顺序加入返回结果
        for(int j=0;j<l.size();j++){
            res[index++]=l.get(j);
        }
    }
    return res;
}

本题解法执行时间为32ms。

Runtime: 32 ms, faster than 91.28% of Java online submissions for Diagonal Traverse II.

Memory Usage: 74.9 MB, less than 100.00% of Java online submissions for Diagonal Traverse II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1424-diagonal-traverse-ii-解题思路分析/
Categories: leetcode
kwantong: