Greedy Solution to Reconstruct a 2-Row Binary Matrix

  • 时间:2020-09-10 13:27:27
  • 分类:网络文摘
  • 阅读:90 次

Given the following details of a matrix with n columns and 2 rows :

The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
The sum of elements of the 0-th(upper) row is given as upper.
The sum of elements of the 1-st(lower) row is given as lower.
The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.
Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.
Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []
Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:
1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Hints:
You cannot do anything about colsum[i] = 2 case or colsum[i] = 0 case. Then you put colsum[i] = 1 case to the upper row until upper has reached. Then put the rest into lower row.
Hide Hint 2
Fill 0 and 2 first, then fill 1 in the upper row or lower row in turn but be careful about exhausting permitted 1s in each row.

C++ Greedy Algorithm to Reconstruct the Binary Matrix

The column count is known. Thus we iterate each column. If the count is two, we know there are two 1’s in original binary matrix. If the count is zero, we know both values in the column are zero.

If it is 1, there are two possibilities. However, we can use the greedy approach – to fill 1 in the row where the row counter is larger.

At any time, if both row counts fall negative, we know there isn’t such binary matrix – return empty.

At the end, we also need to return empty matrix if any of the row counter is positive – meaning that it does not match the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> r(2, vector<int>(colsum.size(), -1));
        for (int i = 0; i < colsum.size(); ++ i) {
            if (colsum[i] == 2) {
                if (--upper < 0) return {};
                if (--lower < 0) return {};
                r[0][i] = 1;
                r[1][i] = 1;
            } else if (colsum[i] == 0) {
                r[0][i] = 0;
                r[1][i] = 0;
            } else {
                if (upper > lower) {
                    r[0][i] = 1;
                    r[1][i] = 0;
                    if (-- upper < 0) return {};
                } else {
                    r[0][i] = 0;
                    r[1][i] = 1;
                    if (-- lower < 0) return {};
                }
            }
        }
        return ((upper == 0) && (lower == 0)) ? r : vector<vector<int>>(0);
    }
};
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> r(2, vector<int>(colsum.size(), -1));
        for (int i = 0; i < colsum.size(); ++ i) {
            if (colsum[i] == 2) {
                if (--upper < 0) return {};
                if (--lower < 0) return {};
                r[0][i] = 1;
                r[1][i] = 1;
            } else if (colsum[i] == 0) {
                r[0][i] = 0;
                r[1][i] = 0;
            } else {
                if (upper > lower) {
                    r[0][i] = 1;
                    r[1][i] = 0;
                    if (-- upper < 0) return {};
                } else {
                    r[0][i] = 0;
                    r[1][i] = 1;
                    if (-- lower < 0) return {};
                }
            }
        }
        return ((upper == 0) && (lower == 0)) ? r : vector<vector<int>>(0);
    }
};

The above C++ code runs at complexity O(N) where N is the number of the column. The space requirement is O(1) constant disregard the output binary matrix.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
网络传闻中的“致癌食物”是否真致癌  冬季食补:最佳的羊肉吃法,你知道吗  鸡汤虽营养丰富,但这几种病人不要喝  饮食健康与胃病食疗(一):胃病患者饮食注意事项  饮食健康与胃病食疗(二):慢性胃炎的饮食调理  饮食健康与胃病食疗(三):这样饮食降低胃癌风险  冬至时节,常吃这几种传统美食可补阳、防寒!  只有这样吃大蒜才能杀菌防癌,以前你吃对了吗  丝瓜营养丰富,其对人体的保健功效如此之多  患有胃病的人常吃这些食物,可以帮助调理好胃 
评论列表
添加评论