原文链接: https://leetcode-cn.com/problems/diagonal-traverse-ii

英文原文

Given a list of lists of integers, 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]

Example 3:

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

Example 4:

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

 

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

中文题目

给你一个列表 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 个数字。

通过代码

高赞题解

解题思路

根据矩形的特点，设行的标号为i，列的标号为j。则对于每一条对角线而言，i + j的值是唯一的。
（可以参考 LeetCode探索 中 “哈希表” 的部分）

知道这一点之后，就可以按照对角线对nums中的值进行聚类。聚类完毕后，将所有的数值生成一个数组即可。

代码

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int len = 0;
		Map<Integer,List<Integer>> map = new TreeMap<>();
		for(int i = 0;i < nums.size();i++) {
			len += nums.get(i).size(); // 获取最后要返回的数组的长度，即元素个数
			for(int j = 0;j < nums.get(i).size();j++) {
				if(map.containsKey(i + j)) {
					map.get(i + j).add(nums.get(i).get(j));
				}
				else {
					List<Integer> list = new ArrayList<>();
					list.add(nums.get(i).get(j));
					map.put(i + j, list);
				}
			}
		}
		int[] ans = new int[len];
		int index = 0;
		for(int key : map.keySet()) { // 遍历map
			List<Integer> list = map.get(key);
			for(int j = list.size() - 1;j >= 0;j--) { // 根据题目的输出要求确定生成数组中元素的顺序
				ans[index] = list.get(j);
				index++;
			}
		}
        return ans;
    }
}

统计信息

通过次数	提交次数	AC比率
7060	17577	40.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言