Medium

题目描述

给你一个二维整数数组 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]

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= sum(nums[i].length) <= 10^5
  • 1 <= nums[i][j] <= 10^5

提示：

  • 注意行索引和列索引之和相等的数字属于同一条对角线
  • 将它们存储在元组 (sum, row, val) 中，排序后重新组合答案

解题思路

这道题要求按对角线顺序遍历不规则的二维数组。关键观察是：同一条对角线上的元素，其行索引和列索引之和相等。

解法分析

方法一：排序法（推荐）

  1. 遍历所有元素，记录 (i+j, i, nums[i][j]) 三元组
  2. 按照 i+j 升序、i 升序的规则排序
  3. 提取排序后的值

方法二：哈希表分组

  1. 按照 i+j 值将元素分组存入哈希表
  2. 对每组内的元素按行索引排序
  3. 按对角线编号顺序输出结果

核心思路：

  • 对角线编号 = 行索引 + 列索引
  • 同一对角线内按行索引升序排列
  • 这样可以保证从左上到右下的对角线遍历顺序

排序法代码更简洁，哈希表法在某些情况下可能有更好的常数因子，但总体复杂度相同。由于题目数据规模较大，推荐使用排序法。

代码实现

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<tuple<int, int, int>> elements;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums[i].size(); j++) {
                elements.push_back({i + j, i, nums[i][j]});
            }
        }
        
        sort(elements.begin(), elements.end());
        
        vector<int> result;
        for (auto& elem : elements) {
            result.push_back(get<2>(elem));
        }
        
        return result;
    }
};

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        elements = []
        
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                elements.append((i + j, i, nums[i][j]))
        
        elements.sort()
        
        return [val for _, _, val in elements]

public class Solution {
    public int[] FindDiagonalOrder(IList<IList<int>> nums) {
        var elements = new List<(int sum, int row, int val)>();
        
        for (int i = 0; i < nums.Count; i++) {
            for (int j = 0; j < nums[i].Count; j++) {
                elements.Add((i + j, i, nums[i][j]));
            }
        }
        
        elements.Sort((a, b) => {
            int cmp = a.sum.CompareTo(b.sum);
            return cmp != 0 ? cmp : a.row.CompareTo(b.row);
        });
        
        var result = new int[elements.Count];
        for (int i = 0; i < elements.Count; i++) {
            result[i] = elements[i].val;
        }
        
        return result;
    }
}

var findDiagonalOrder = function(nums) {
    let elements = [];
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums[i].length; j++) {
            elements.push([i + j, i, nums[i][j]]);
        }
    }
    
    elements.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    
    return elements.map(elem => elem[2]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N log N)N 是所有元素总数，排序需要 O(N log N)
空间复杂度O(N)存储所有元素的三元组信息