1329. 将矩阵按对角线排序

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

示例 1：

img

1
2

输入：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：

1
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

普通题，但是耗时太久.

思路就是按照提示找到同一斜边的元素，arraylist排序，写回去。

问题在于找到同一斜边的元素，注意边界。我将遍历过程分成两段，分别是下三角和上三角，利用mat[i][j]的条件i<m&&j<n来控制边界。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

  public static int[][] diagonalSort(int[][] mat) {
        int m=mat.length;
       // System.out.println(m);
        int n=mat[0].length;
        //System.out.println(n);
        if(m==1|n==1) return mat;
        for(int i=m-1;i>=0;i--){
            ArrayList<Integer> s=new ArrayList<Integer>();
            for(int j=0;i+j<m&&j<n;j++){
                s.add(mat[i+j][j]);
            }
           // System.out.println(s);
            s.sort(Comparator.naturalOrder());
            //System.out.println(s);
            for(int j=0;i+j<m&&j<n;j++){
                mat[i+j][j]=s.get(j);
            }
        }
        System.out.println("-----------------");
        for(int i=0;i<n+1;i++){
            ArrayList<Integer> s=new ArrayList<Integer>();
            int i2=0;
            for(int j=i+1;(j<n)&&(i2<m);j++,i2++){
               // System.out.println("i2="+i2+" j="+j);
                s.add(mat[i2][j]);

            }
           // System.out.println(s);
            s.sort(Comparator.naturalOrder());
           // System.out.println(s);
            i2=0;
            for(int j=i+1;(j<n)&&(i2<m);j++,i2++){
                //System.out.println("i2="+i2+" j="+j);
                mat[i2][j]=s.get(i2);

            }
        }

        return  mat;
    }

看了题解，所有的同一斜边的元素有一个共同特征：i和j的差为定值，也就是说，给定i，j唯一确定是哪一条对角线，一共m+n-1个对角线，创建m+n-1个arraylist。

对每一条对角线上的元素进行排序。

填回去的操作：按照从左到右，从上往下遍历时，每次都是最小的在前，可以另外用一个数组保存，或者也可以将arraylist转成栈，按次序填回去的数一定是从小到大的。

别人的code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public int[][] diagonalSort(int[][] mat) {
        // 行数
        int m = mat.length;
        // 列数
        int n = mat[0].length;
        // 主对角线的条数
        int dLen = m + n - 1;

        // 每一条对角线都创建一个动态数组
        ArrayList<Integer>[] diagonal = new ArrayList[dLen];
        for (int i = 0; i < dLen; i++) {
            diagonal[i] = new ArrayList<>(m);
        }

        // 遍历原始矩阵，把原始矩阵中的元素放进对应的动态数组中
        // 主对角线上元素的特点是：纵坐标 - 横坐标 = 定值
        // 加上偏移 m - 1 是为了能够放进数组中
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diagonal[j - i + (m - 1)].add(mat[i][j]);
            }
        }

        // 对每一个对角线上的动态数组分别进行升序排序
        for (int i = 0; i < dLen; i++) {
            Collections.sort(diagonal[i]);
        }

        int[][] res = new int[m][n];

        // 对角线数组上还未取出的元素的下标，初始化的时候均为 0
        int[] next = new int[dLen];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 对角线的坐标
                int index = j - i + (m - 1);
                // 记录结果
                res[i][j] = diagonal[index].get(next[index]);
                // 维护 next 数组的值
                next[index]++;
            }
        }
        return res;
    }

作者：Code_respect
链接：https://leetcode-cn.com/problems/sort-the-matrix-diagonally/solution/javati-jie-by-code_respect-66zw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。