LEETCODE 1329. Sort the Matrix Diagonally 解题思路分析

题目大意:

将矩阵按对角线排序

给你一个 m * 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]]

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1329

解题思路分析:

本题没想到太好的办法,基本上是利用暴力解来排序。首先遍历矩阵的每一条斜线,斜线的顶点分别是矩阵左边和上边上的每一个点,将每条斜线上的点保存至PriorityQueue中,由于PriorityQueue是自动排序的,因此在遍历完一条斜线后,按顺序取出PriorityQueue中的每一个值,再将其插入返回结果的相应位置上即可。

实现代码:

public int[][] diagonalSort(int[][] mat) {
    // 返回结果
    int[][] res = new int[mat.length][mat[0].length];
    // 遍历左边上每个点开头的斜线
    for(int r=0;r<mat.length;r++){
        // 对该斜线上的数字排序,并输出到返回结果
        sort(r,0,res,mat);
    }
    // 遍历上边上每个点开头的斜线
    for(int c=1;c<mat[0].length;c++){
        // 对该斜线上的数字排序,并输出到返回结果
        sort(0,c,res,mat);
    }
    return res;
}

void sort(int r, int c, int[][] res, int[][] mat){
    // 保存该斜线上的所有数字
    PriorityQueue<Integer> q=new PriorityQueue<>();
    // 当前斜线起点
    int row=r, col=c;
    // 遍历斜线上每一点
    while(row<mat.length&&col<mat[0].length){
        // 将每个元素加入Queue
        q.offer(mat[row][col]);
        // 行列分别加一
        row++;
        col++;
    }
    // 返回斜线顶点
    row=r;
    col=c;
    // 遍历斜线上每一点
    while(row<mat.length&&col<mat[0].length){
        // 按顺序从Queue中取出排序好的元素,并赋值到该点
        res[row][col]=q.poll();
        // 行列分别加一
        row++;
        col++;
    }
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 92.86% of Java online submissions for Sort the Matrix Diagonally.

Memory Usage: 41.5 MB, less than 100.00% of Java online submissions for Sort the Matrix Diagonally.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1329-sort-the-matrix-diagonally-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。