Diagonal Traverse II ใน C++

สมมติว่าเรามี list of lists nums เราต้องแสดงทุก element ใน diagonal order

ตัวอย่าง: [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] ผลลัพธ์: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

วิธีแก้ปัญหา

1. เก็บ (value, row, col) ของทุก element
2. เรียงตาม (row+col) แล้ว row มากกว่า (descending) เพื่อให้ได้ diagonal order
3. ดึง value ตามลำดับที่เรียงแล้ว

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

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

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

class Solution { 
public: 
    static bool cmp(vector<int>& a, vector<int>& b ){ 
        int sum1 = a[1] + a[2]; 
        int sum2 = b[1] + b[2]; 
        return sum1 == sum2 ? a[1] > b[1] : sum1 < sum2; 
    } 
    
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) { 
        vector<int> ret; 
        vector<vector<int>> v; 
        for (int i = 0; i < nums.size(); i++) { 
            for (int j = 0; j < nums[i].size(); j++) { 
                v.push_back({ nums[i][j], i, j }); 
            } 
        } 
        sort(v.begin(), v.end(), cmp); 
        for (auto& it : v) ret.push_back(it[0]); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}; 
    print_vector(ob.findDiagonalOrder(v)); 
}

ข้อมูลนำเข้า

{{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}

ผลลัพธ์

[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16, ]