Sắp xếp ma trận theo đường chéo trong C++

Cho ma trận kích thước N x M, ta cần sắp xếp các phần tử theo đường chéo từ góc trên bên trái xuống góc dưới bên phải theo thứ tự tăng dần.

Ví dụ minh họa

Ma trận đầu vào:

Ma trận sau khi sắp xếp:

Thuật toán

1. Định nghĩa hàm solve(si, sj, mat) để xử lý một đường chéo bắt đầu từ vị trí (si, sj).
2. Lấy số hàng n và số cột m của ma trận.
3. Tạo mảng tạm temp để lưu các phần tử trên đường chéo.
4. Duyệt từ (si, sj) theo hướng chéo xuống phải (i++, j++) cho đến khi hết ma trận, đưa các phần tử vào temp.
5. Sắp xếp mảng temp theo thứ tự tăng dần.
6. Gán lại các giá trị từ temp trở lại ma trận theo cùng đường chéo đó.

Gọi hàm từ main

• Duyệt tất cả đường chéo bắt đầu từ cột 0: for i = 0 đến n-1: solve(i, 0, mat)
• Duyệt tất cả đường chéo bắt đầu từ hàng 0 (bỏ qua (0,0) đã xử lý): for j = 1 đến m-1: solve(0, j, mat)

Ví dụ code C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> 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<vector<int>> &mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<int> temp;
        int i = si, j = sj;
        
        // Thu thập phần tử trên đường chéo
        while (i < n && j < m) {
            temp.push_back(mat[i][j]);
            i++; j++;
        }
        
        // Sắp xếp
        sort(temp.begin(), temp.end());
        
        // Gán lại
        int idx = 0;
        i = si; j = sj;
        while (i < n && j < m) {
            mat[i][j] = temp[idx++];
            i++; j++;
        }
    }
    
    vector<vector<int>> diagonalSort(vector<vector<int>>& 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<vector<int>> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    Solution ob;
    print_vector(ob.diagonalSort(v));
    return 0;
}

Đầ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]]