Medium

题目描述

矩阵对角线是指从矩阵最顶行或最左列的某个单元格开始，向右下方向延伸直到矩阵末端的对角线单元格。例如，在一个 6 x 3 的矩阵中，从 mat[2][0] 开始的矩阵对角线包括单元格 mat[2][0]、mat[3][1] 和 mat[4][2]。

给定一个 m x n 的整数矩阵 mat，请将每条矩阵对角线按升序排序，并返回排序后的矩阵。

示例 1：

输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

示例 2：

输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • 1 <= mat[i][j] <= 100

解题思路

解题思路

这道题的核心是识别每条对角线并对其进行排序。关键观察是：同一条对角线上的所有元素，其行索引与列索引的差值（i - j）是相同的。

方法一：哈希表存储（推荐）

  1. 遍历矩阵，使用 i - j 作为键，将每条对角线的元素存储在哈希表中
  2. 对每条对角线的元素进行排序
  3. 重新遍历矩阵，从排序后的对角线中依次取出元素填回原位置

方法二：直接排序

对于每条对角线，找到起始位置，收集所有元素，排序后写回。

两种方法的时间复杂度相同，但方法一更简洁易懂，代码可读性更好。

例如在示例1中：

  • 对角线 i-j=-1：[3,2,1] → 排序后：[1,2,3]
  • 对角线 i-j=0：[3,2,1] → 排序后：[1,2,3]
  • 对角线 i-j=1：[1,1,2] → 排序后：[1,1,2]

通过这种索引方式，我们可以高效地处理所有对角线。

代码实现

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, vector<int>> diagonals;
        
        // 收集每条对角线的元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diagonals[i - j].push_back(mat[i][j]);
            }
        }
        
        // 对每条对角线排序
        for (auto& [key, diagonal] : diagonals) {
            sort(diagonal.begin(), diagonal.end());
        }
        
        // 重新分配排序后的元素
        unordered_map<int, int> indices;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                mat[i][j] = diagonals[key][indices[key]++];
            }
        }
        
        return mat;
    }
};

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict
        
        m, n = len(mat), len(mat[0])
        diagonals = defaultdict(list)
        
        # 收集每条对角线的元素
        for i in range(m):
            for j in range(n):
                diagonals[i - j].append(mat[i][j])
        
        # 对每条对角线排序
        for key in diagonals:
            diagonals[key].sort()
        
        # 重新分配排序后的元素
        indices = defaultdict(int)
        for i in range(m):
            for j in range(n):
                key = i - j
                mat[i][j] = diagonals[key][indices[key]]
                indices[key] += 1
        
        return mat

public class Solution {
    public int[][] DiagonalSort(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        var diagonals = new Dictionary<int, List<int>>();
        
        // 收集每条对角线的元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                if (!diagonals.ContainsKey(key)) {
                    diagonals[key] = new List<int>();
                }
                diagonals[key].Add(mat[i][j]);
            }
        }
        
        // 对每条对角线排序
        foreach (var kvp in diagonals) {
            kvp.Value.Sort();
        }
        
        // 重新分配排序后的元素
        var indices = new Dictionary<int, int>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                if (!indices.ContainsKey(key)) {
                    indices[key] = 0;
                }
                mat[i][j] = diagonals[key][indices[key]++];
            }
        }
        
        return mat;
    }
}

var diagonalSort = function(mat) {
    const m = mat.length, n = mat[0].length;
    const diagonals = new Map();
    
    // 收集每条对角线的元素
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            if (!diagonals.has(key)) {
                diagonals.set(key, []);
            }
            diagonals.get(key).push(mat[i][j]);
        }
    }
    
    // 对每条对角线排序
    for (let [key, diagonal] of diagonals) {
        diagonal.sort((a, b) => a - b);
    }
    
    // 重新分配排序后的元素
    const indices = new Map();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            if (!indices.has(key)) {
                indices.set(key, 0);
            }
            const idx = indices.get(key);
            mat[i][j] = diagonals.get(key)[idx];
            indices.set(key, idx + 1);
        }
    }
    
    return mat;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n×log(min(m,n)))遍历矩阵需要O(m×n)，每条对角线最多有min(m,n)个元素，排序需要O(min(m,n)×log(min(m,n)))，共有m+n-1条对角线
空间复杂度O(m×n)需要额外的哈希表存储所有对角线元素

相关题目