思路:
根据题目,可得出如下关键条件:
1.返回的这个二进制矩阵里面的元素不是0就是1;
2.colsum数组中的元素最大为2,最小为0;
3.返回的二进制矩阵只有两行,列数与colsum数组相同。
根据所有的条件,我们可以采用贪心算法策略 + 两次扫描即可解决本问题,第一次扫描先填充colsum数组中元素为2的对应的列数,填充的同时需要依次将upper和lower减减。第二次扫描再满足colsum数组中元素为1的情况,upper更大就先填充第一行,否则填充第二行。两次遍历完后,如果这个二维矩阵是符合条件的,那么upper和lower都应为0,否则为无效答案,应该返回一个空数组。
TypeScript源代码:
function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
const len: number = colsum.length;
const ans: number[][] = new Array(2).fill(0).map((item) => {return item = new Array(len).fill(0);});
for(let i = 0; i < len; ++i) {
if(colsum[i] === 2) {
ans[0][i] = 1;
ans[1][i] = 1;
upper--;
lower--;
}
}
for(let i = 0; i < len; ++i) {
if(ans[0][i] === 0 && ans[1][i] === 0
&& colsum[i] === 1) {
if(upper > lower) {
ans[0][i] = 1;
upper--;
} else {
ans[1][i] = 1;
lower--;
}
}
}
if(upper !== 0 || lower !== 0) {
return [];
}
return ans;
};