LeetCode - 1329 将矩阵按对角线排序【排序】

1329. 将矩阵按对角线排序

示例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

思路

  题意：将二维数组按照对角线方向对其排序。

  方法：可以看到数据范围是[1,100]，分布范围很小，可以使用计数排序。其次，对角线方向读取方法可以将整个二维数组分为上三角和下三角两个部分。设置起始偏移量k以及两个索引i和j，让i, j不断加1，直至到达边界。读取数据后存储至计数数组中，再从小到大读取数据填回原数组。

代码

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        for (int k = 0; k < mat.length; k++) {
            int i = 0;
            int j = 0;
            int[] nums = new int[101];
            while (i + k < mat.length && j < mat[0].length) {
                nums[mat[i+k][j]]++;
                i++;
                j++;
            }
            i = 0;
            j = 0;
            for (int l = 1; l <= 100; l++) {
                while (nums[l] != 0) {
                    mat[i+k][j] = l;
                    nums[l]--;
                    i++;
                    j++;
                }
            }
        }
        for (int k = 1; k < mat[0].length; k++) {
            int i = 0;
            int j = 0;
            int[] nums = new int[101];
            while (i  < mat.length && j + k < mat[0].length) {
                nums[mat[i][j+k]]++;
                i++;
                j++;
            }
            i = 0;
            j = 0;
            for (int l = 1; l <= 100; l++) {
                while (nums[l] != 0) {
                    mat[i][j+k] = l;
                    nums[l]--;
                    i++;
                    j++;
                }
            }
        }
        return mat;
    }
}

运行结果