LeetCode- 1329. 将矩阵按对角线排序_1329将矩阵按对角线排序c++

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

#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        vector<int> temp;
        for(int i=0;i<mat.size();i++){
            GetHVec(i,0,temp,mat);
        }
 
        for(int j=0;j<mat[0].size();j++){
            GetWVec(0,j,temp,mat);
        }
 
        for(int i=0;i<vec_height.size();i++){
            QuickSort(vec_height[i],0,vec_height[i].size()-1);
        }
 
        for(int i=0;i<vec_width.size();i++){
            QuickSort(vec_width[i],0,vec_width[i].size()-1);
        }
 
        for(int i=0;i<mat.size();i++){
            restore(i,0,vec_height[i],mat);
        }
 
        for(int j=0;j<mat[0].size();j++){
            restore(0,j,vec_width[j],mat);
        }
 
        return mat;
    }
 
private:
    vector<vector<int>> vec_height;
    vector<vector<int>> vec_width;
 
    void QuickSort(vector<int>& a, int left, int right){
        int i = left;
        int j = right;
        int key = a[i];
        if(left<right){
            while(i<j){
                while(i<j && a[j]>=key){
                    j--;
                }
                a[i] = a[j];
                while(i<j && a[i]<=key){
                    i++;
                }
                a[j] = a[i];
            }
            a[i] = key;
            QuickSort(a,left,j-1);
            QuickSort(a,i+1,right);
        }else{
            return;
        }
    }
 
    void GetHVec(int i, int j, vector<int> &temp, vector<vector<int>>& mat){
        if(i >= mat.size() || j>= mat[i].size()){
            vec_height.push_back(temp);
            temp.clear();
            return;
        }
        temp.push_back(mat[i][j]);
        GetHVec(i+1,j+1,temp,mat);
    }
 
    void GetWVec(int i, int j, vector<int> &temp, vector<vector<int>>& mat){
        if(i >= mat.size()|| j>= mat[i].size()){
            vec_width.push_back(temp);
            temp.clear();
            return;
        }
        temp.push_back(mat[i][j]);
        GetWVec(i+1,j+1,temp,mat);
    }
 
    void restore(int x, int y, vector<int> &val,vector<vector<int>>& mat){
        for(int i=0;i<val.size();i++){
            mat[x++][y++] = val[i];
        }
    }
};
 
 
 
int main(){
 
    vector<vector<int>> mat={{3,3,1,1},
                             {2,2,1,2},
                             {1,1,1,2}};
 
    Solution *ps = new Solution();
    vector<vector<int>>res = ps->diagonalSort(mat);
 
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size();j++){
            cout<<res[i][j]<<",";
        }
        cout<<endl;
    }
 
    return 0;
}