Duyệt chéo II (Diagonal Traverse II) trong C++

Cho danh sách các danh sách nums (mảng răng cưa). Duyệt tất cả phần tử theo thứ tự chéo: các phần tử cùng tổng chỉ số i+j được nhóm lại, trong nhóm sắp theo hàng i giảm dần (tức là từ dưới lên trên).

Ví dụ

Đầu vào: [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Đầu ra: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Thuật toán sắp xếp theo khóa (i+j, -i)

1. Thu thập tất cả phần tử thành tuple {value, i, j}.
2. Sắp xếp theo: i+j tăng, nếu bằng thì i giảm.
3. Trích xuất giá trị theo thứ tự đã sắp xếp.

Triển khai C++

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

class Solution {
public:
    vector findDiagonalOrder(vector>& nums) {
        vector> 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(), [](auto& a, auto& b) {
            int s1 = a[1] + a[2], s2 = b[1] + b[2];
            return s1 == s2 ? a[1] > b[1] : s1 < s2;
        });
        vector res;
        for (auto& e : v) res.push_back(e[0]);
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N log N) với N tổng số phần tử (do sort).
• Không gian: O(N) lưu mảng tuple.

Kết quả kiểm thử

Đầu vào: {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}
Đầu ra: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]