Chương trình sắp xếp các phần tử đường chéo của ma trận tăng dần trong C++

Cho ma trận n x m, sắp xếp các phần tử trên mỗi đường chéo (từ góc trên-trái đến dưới-phải) theo thứ tự tăng dần.

Ví dụ

Ma trận đầu vào:
[[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Ma trận sau khi sắp xếp:
[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Thuật toán

1. Định nghĩa hàm solve(si, sj, mat) xử lý đường chéo bắt đầu từ (si, sj):
   • Thu thập các phần tử trên đường chéo vào mảng temp.
   • Sắp xếp temp.
   • Ghi ngược lại vào ma trận.
2. Gọi solve(i, 0) cho mọi hàng i.
3. Gọi solve(0, j) cho mọi cột j (bắt đầu từ 1).
4. Trả về ma trận đã sửa đổi.

Mã nguồn C++

#include 
using namespace std;

void print_vector(vector> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    void solve(int si, int sj, vector> &mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector temp;
        int i = si, j = sj;
        while (i < n && j < m) {
            temp.push_back(mat[i][j]);
            i++; j++;
        }
        sort(temp.begin(), temp.end());
        i = si; j = sj;
        int idx = 0;
        while (i < n && j < m) {
            mat[i][j] = temp[idx];
            i++; j++; idx++;
        }
    }
    vector> diagonalSort(vector>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        for (int i = 0; i < n; i++) solve(i, 0, mat);
        for (int j = 1; j < m; j++) solve(0, j, mat);
        return mat;
    }
};

int main() {
    vector> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    Solution ob;
    print_vector(ob.diagonalSort(v));
}

Đầu vào / Đầu ra

Input: {{3,3,1,1},{2,2,1,2},{1,1,1,2}}
Output: [[1,1,1,1], [1,2,2,2], [1,2,3,3]]