Tái tạo ma trận nhị phân 2 hàng trong C++

Mô tả bài toán

Cho ma trận 2 hàng, n cột, các phần tử 0/1. Biết:

• Tổng hàng 0 (trên) = upper.
• Tổng hàng 1 (dưới) = lower.
• Tổng cột i = colsum[i].

Tái tạo ma trận thỏa mãn. Nếu không có giải pháp, trả về mảng rỗng.

Ví dụ: upper=2, lower=1, colsum=[1,1,1] → [[1,1,0],[0,0,1]].

Giải thuật Tham lam

1. Duyệt từng cột:
   • Nếu colsum[i] == 2: cả 2 hàng đều đặt 1, giảm upper--, lower--.
   • Nếu colsum[i] == 1: đặt 1 ở hàng có tổng còn lại lớn hơn (ưu tiên hàng trên nếu bằng nhau).
   • Nếu colsum[i] == 0: cả 2 đều 0.
2. Nếu cuối upper != 0 hoặc lower != 0 hoặc có xung đột → trả về rỗng.

Cài đặt C++

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

void print_matrix(vector<vector<int>> v) {
    cout << "[";
    for (auto& row : v) {
        cout << "[";
        for (int x : row) cout << x << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> ans(2, vector<int>(n));
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (--upper < 0 || --lower < 0) return {};
                ans[0][i] = ans[1][i] = 1;
            } else if (colsum[i] == 1) {
                if (upper > lower) { ans[0][i] = 1; upper--; }
                else if (lower > upper) { ans[1][i] = 1; lower--; }
                else if (upper > 0) { ans[0][i] = 1; upper--; }
                else if (lower > 0) { ans[1][i] = 1; lower--; }
                else return {};
            }
        }
        if (upper != 0 || lower != 0) return {};
        return ans;
    }
};

int main() {
    vector<int> v = {1,1,1};
    Solution ob;
    print_matrix(ob.reconstructMatrix(2, 1, v));
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(n) cho ma trận kết quả.