秋招每日一题T14——将矩阵按对角线排序

题目描述

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-the-matrix-diagonally
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

〇本题有两种解法，第一种就是先将矩阵中每个左对角线上的元素取出存到vector中，然后排序，最后再存回原来的数组中，最朴素的想法。另一种解法则是妙手。
①妙手的思路是这样的，左对角线上的元素具有这样的性质：位于同一条左对角线上的元素，其i-j值均相同。 （右对角线上的元素i+j相同）
② 由①，可以使用哈希，存储矩阵i-j上的元素，之后再排序，放回原矩阵即可。

代码（朴素）

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n,m;
        n = mat.size();
        m = mat[0].size();
        
        for(int b=1-n;b<=m-1;b++){
            vector<int> q;
            for(int x=0,y=b;x<n&&y<m;x++,y++){
                if(y >= 0){
                    q.push_back(mat[x][y]);
                }
            }
            sort(q.begin(),q.end());
            for(int x=0,y=b,k=0;x<n&&y<m;x++,y++){
                if(y>=0){
                    mat[x][y] = q[k++];
                }
            }
        }
        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

代码（妙手）

①用vector.rbegin()和vector.rend()进行排序，效果是将vector中的元素进行了逆向排序（降序排序）。
②降序排序的目的是vector可以向栈一样在结尾追加(push_back())和弹出(back(), pop_back())。

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        unordered_map<int,vector<int>> q;
        int n = mat.size(),m = mat[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                q[i-j].push_back(mat[i][j]);
            }
        }
        for(auto& v:q)  sort(v.second.rbegin(),v.second.rend());
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                mat[i][j] = q[i-j].back();
                q[i-j].pop_back();
            }
        }
        return mat;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20