[LeetCode 1329]按矩阵对角线进行排序_将矩阵按对角线排序

不积跬步，无以至千里

将矩阵按对角线排序

描述

给你一个 m * n 的整数矩阵 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]]

原题链接

思路

根据矩阵的特点，我们可以将其以大对角线划分为两部分，再分别遍历这两部分进行冒泡排序。

看图：
矩阵按大对角线划分成上下两部分

然后分别遍历上下两部分，对每一条对角线上的元素进行冒泡排序

代码

public class Main {
    public static int[][] diagonalSort(int[][] mat) {
        int rows=mat.length;
        int columns=mat[0].length;

        //先排有上半部分，从(0,0)开始
        for (int i = 0; i < columns; i++) {
            toSort(0,i,rows,columns,mat);
        }

        //排左下半部分，(0,0)已经排过了，所以从(1,0)开始
        for (int i = 1; i < rows; i++) {
            toSort(i,0,rows,columns,mat);
        }
        return mat;
    }


    //冒泡排序
    //对角线上的元素坐标都是：[i+1][j+1]式递进
    private static int[][] toSort(int i,int j, int rows, int columns, int[][] mat) {
        for (; i< rows-1 && j<columns-1; i++,j++) {
            for (int k = i+1,m=j+1; k < rows && m<columns; k++,m++) {
                if (mat[k][m]<mat[i][j]){
                	//交换
                    int temp=mat[k][m];
                    mat[k][m]=mat[i][j];
                    mat[i][j]=temp;
                }
            }
        }
        return mat;
    }
 }
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

学到了，学到了！
(这是刷题途中学到的思路，加以整理方便复习，希望本菜鸟可早日从"暴力"选手转型，冲冲冲！)