[LeetCode] 1424. Diagonal Traverse II

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

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

Constraints:
1 <= nums.length <= 105
1 <= nums[i].length <= 105
1 <= sum(nums[i].length) <= 105
1 <= nums[i][j] <= 105

对角线遍历 II。

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

思路

这道题跟版本一类似，还是让我们以对角线分组输出矩阵中的值。我们可以把 i + j 当做 key 放入一个 hashmap，因为在同一条对角线上的元素的 i + j 的值是相同的，所以我们可以这样分组。注意因为我们对整个二维 list 是逐行扫描的所以当我们加入元素的时候，元素需要被加入他所在 hashmap 那条对角线的第一个，这样顺序才不会乱。

复杂度

时间O(mn)
空间O(mn) - output有这么多元素

代码

Java实现

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
		int count = 0;
		for (int i = 0; i < nums.size(); i++) {
			for (int j = 0; j < nums.get(i).size(); j++) {
				map.putIfAbsent(i + j, new ArrayList<>());
				map.get(i + j).add(0, nums.get(i).get(j));
				count++;
			}
		}

		int[] res = new int[count];
		int index = 0;
		for (int key = 0; key <= map.size(); key++) {
			if (map.containsKey(key)) {
				for (int val : map.get(key)) {
					res[index++] = val;
				}
			}
		}
		return res;
    }
}