การจัดเรียงเมทริกซ์แบบแนวทแยงใน C++

สมมติว่าเรามีเมทริกซ์ขนาด N x M เราต้องจัดเรียงเมทริกซ์นี้แบบแนวทแยงจากมุมซ้ายบนไปยังมุมขวาล่างในลำดับเพิ่มขึ้น ตัวอย่างเช่น หากเมทริกซ์มีค่าดังนี้:

เมทริกซ์ผลลัพธ์จะเป็น:

ขั้นตอนการแก้ปัญหา

1. กำหนดเมธอด solve() ที่รับพารามิเตอร์ si, sj และเมทริกซ์ mat
2. n := จำนวนแถว และ m := จำนวนคอลัมน์
3. สร้างอาร์เรย์ temp
4. i := si, j := sj, index := 0
5. วนลูป while i < n และ j < m:
   • นำค่า mat[i][j] ใส่ใน temp แล้วเพิ่ม i และ j ทีละ 1
6. จัดเรียงอาร์เรย์ temp
7. ตั้งค่า index := 0, i := si, j := sj
8. วนลูป while i < n และ j < m:
   • mat[i][j] := temp[index]
   • เพิ่ม i, j และ index ทีละ 1
9. จากเมธอดหลัก:
   • n := จำนวนแถว, m := จำนวนคอลัมน์
   • วนลูป i จาก 0 ถึง n-1: เรียก solve(i, 0, mat)
   • วนลูป j จาก 1 ถึง m-1: เรียก solve(0, j, mat)
   • คืนค่า mat

ตัวอย่างโค้ด (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, idx = 0;
        
        while(i < n && j < m) {
            temp.push_back(mat[i][j]);
            i++; j++;
        }
        
        sort(temp.begin(), temp.end());
        
        idx = 0; i = si; j = sj;
        while(i < n && j < m) {
            mat[i][j] = temp[idx];
            i++; j++; idx++;
        }
    }
    
    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;
}

อินพุต

[[3,3,1,1],[2,2,1,2],[1,1,1,2]]

เอาต์พุต

[[1,1,1,1],[1,2,2,2],[1,2,3,3]]