Reconstruct a 2-Row Binary Matrix 重構(gòu) 2 行二進(jìn)制矩陣

問題描述：

給你一個 2 行 n 列的二進(jìn)制數(shù)組：

矩陣是一個二進(jìn)制矩陣，這意味著矩陣中的每個元素不是 0 就是 1。
第 0 行的元素之和為 upper。
第 1 行的元素之和為 lower。
第 i 列（從 0 開始編號）的元素之和為 colsum[i]，colsum 是一個長度為 n 的整數(shù)數(shù)組。
你需要利用 upper，lower 和 colsum 來重構(gòu)這個矩陣，并以二維整數(shù)數(shù)組的形式返回它。

如果有多個不同的答案，那么任意一個都可以通過本題。

如果不存在符合要求的答案，就請返回一個空的二維數(shù)組。

$$\begin{gathered} 1<=colsum.length<=10^5 \\ 0<=upper,lower<=colsum.length \\ 0<=colsum[i]<=2 \end{gathered}$$

$k,nums.length范圍[1,16],nums.length$

分析

目標(biāo)是構(gòu)建出一個2行的二進(jìn)制數(shù)組，并且第一行的$sum1=upper$,第二行的$sum2=lower$.并且2行相同位置的加和$arr1[i]+arr2[i]==colsum[i]$.

當(dāng)然也可能無法構(gòu)建符合給定條件的數(shù)組。

假設(shè)存在這樣的目標(biāo)數(shù)組arr，那么必須滿足
第一個限制
$$\sum _{0<=k<=n}(arr1[k]+arr2[k])=upper+lower.$$

此外就要看數(shù)據(jù)是否能夠分配合理，觀察可以知道，當(dāng)$colsum[i]==0or2$,可以確定$arr[i]$的數(shù)值，即同0，2.
所以另一個限制就是$colsum$中$2$出現(xiàn)的次數(shù).
$$cnt2<=\min (upper,lower).$$

所以當(dāng)上述2個條件都滿足的情況下，是完全可以構(gòu)造成功。

策略貪心

把都減掉$cnt2$，即2出現(xiàn)的次數(shù)，剩余的就是各行1出現(xiàn)的次數(shù)。
所以當(dāng)$colsum[i]==1$,可以先放行1，當(dāng)$upper$降低為0，就可以把剩余的都放入行2。

代碼

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        int sum = 0, two = 0;
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                ++two;
            }
            sum += colsum[i];
        }
        if (sum != upper + lower || Math.min(upper, lower) < two) {
            return new ArrayList<List<Integer>>();
        }
        upper -= two;
        lower -= two;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < 2; ++i) {
            res.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                res.get(0).add(1);
                res.get(1).add(1);
            } else if (colsum[i] == 1) {
                if (upper > 0) {
                    res.get(0).add(1);
                    res.get(1).add(0);
                    --upper;
                } else {
                    res.get(0).add(0);
                    res.get(1).add(1);
                }
            } else {
                res.get(0).add(0);
                res.get(1).add(0);
            }
        }
        return res;
    }
}
 

時間復(fù)雜度$O(N)$

空間復(fù)雜度$O(1)$

Tag

Matrix
Greedy文章來源地址http://www.zghlxwxcb.cn/news/detail-526484.html

到了這里，關(guān)于【算法】Reconstruct a 2-Row Binary Matrix 重構(gòu) 2 行二進(jìn)制矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！