โปรแกรมจัดเรียงองค์ประกอบแต่ละเส้นทแยงในเมทริกซ์เป็นลำดับเพิ่มขึ้นใน C++

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

เช่น ถ้าอินพุตเมทริกซ์เป็น [[3,3,1,1],[2,2,1,2],[1,1,1,2]] เมทริกซ์เอาต์พุตจะเป็น [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

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

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

ตัวอย่างโค้ด

#include 
using namespace std;
void print_vector(vector> v){
    cout << "[";
    for(int i = 0; i> &mat){
        int n = mat.size();
        int m = mat[0].size();
        vector temp;
        int i = si;
        int j = sj;
        int 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> 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));
}

อินพุต

{{3,3,1,1},{2,2,1,2},{1,1,1,2}}

เอาต์พุต

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