題目

給你一個 2 行 n 列的二進位制陣列：

矩陣是一個二進位制矩陣，這意味著矩陣中的每個元素不是 0 就是 1。

第 0 行的元素之和為 upper。

第 1 行的元素之和為 lower。

第 i 列（從 0 開始編號）的元素之和為 colsum[i]，colsum 是一個長度為 n 的整數陣列。

你需要利用 upper，lower 和 colsum 來重構這個矩陣，並以二維整數陣列的形式返回它。

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

如果不存在符合要求的答案，就請返回一個空的二維陣列。

示例 1：輸入：upper = 2, lower = 1, colsum = [1,1,1] 輸出：[[1,1,0],[0,0,1]]

解釋：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正確答案。

示例 2：輸入：upper = 2, lower = 3, colsum = [2,2,1,1] 輸出：[]

示例 3：輸入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]

輸出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

提示：1 <= colsum.length <= 10^5

0 <= upper, lower <= colsum.length

0 <= colsum[i] <= 2

解題思路分析

1、貪心；時間複雜度O(n)，空間複雜度O(n)

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {	res := make([][]int, 0)	total := 0	two := 0	for i := 0; i < len(colsum); i++ {		total = total + colsum[i]		if colsum[i] == 2 {			two++		}	}	if total != upper+lower || two > upper || two > lower {		return nil	}	up := make([]int, len(colsum))	down := make([]int, len(colsum))	upper = upper - two // 上面陣列單獨1的個數	for i := 0; i < len(colsum); i++ {		if colsum[i] == 2 { // 2=>各填充1			up[i] = 1			down[i] = 1			lower--		} else if colsum[i] == 1 {			if upper > 0 { // 先填充上面陣列				up[i] = 1				upper--			} else {				down[i] = 1			}		}	}	res = append(res, up, down)	return res}

2、貪心；時間複雜度O(n)，空間複雜度O(n)

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {	res := make([][]int, 0)	up := make([]int, len(colsum))	down := make([]int, len(colsum))	upSum := 0	lowSum := 0	total := 0	for i := 0; i < len(colsum); i++ {		total = total + colsum[i]		if colsum[i] == 2 { // 2=>各填充1			up[i] = 1			down[i] = 1			upSum++			lowSum++		}	}	if upSum > upper || lowSum > lower || total != upper+lower {		return nil	}	for i := 0; i < len(colsum); i++ {		if colsum[i] == 1 {			if upSum < upper {				up[i] = 1				upSum++			} else {				down[i] = 1			}		}	}	res = append(res, up, down)	return res}

總結

Medium題目，先統計個數是否匹配的上，然後2的情況2個數組都放，剩下1的情況，根據上面陣列的情況來放