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;
}
}