网站建设推广员工资,wordpress文章里面的菜单怎么添加,化妆品网站建设版块,外链来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你两个非负整数数组 rowSum 和 colSum #xff0c;其中 rowSum[i] 是二维矩阵中第 i 行元素的和#xff0c; colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素#xff0c;但是你知…来源力扣LeetCode
描述
给你两个非负整数数组 rowSum 和 colSum 其中 rowSum[i] 是二维矩阵中第 i 行元素的和 colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵题目保证存在 至少一个 可行矩阵。
示例 1
输入rowSum [3,8], colSum [4,7]
输出[[3,0],[1,7]]
解释
第 0 行3 0 3 rowSum[0]
第 1 行1 7 8 rowSum[1]
第 0 列3 1 4 colSum[0]
第 1 列0 7 7 colSum[1]
行和列的和都满足题目要求且所有矩阵元素都是非负的。
另一个可行的矩阵为[[1,2],[3,5]]示例 2
输入rowSum [5,7,10], colSum [8,6,8]
输出[[0,5,0],[6,1,0],[2,0,8]]示例 3
输入rowSum [14,9], colSum [6,9,8]
输出[[0,9,5],[6,0,3]]示例 4
输入rowSum [1,0], colSum [1]
输出[[1],[0]]示例 5
输入rowSum [0], colSum [0]
输出[[0]]提示
1 rowSum.length, colSum.length 5000 rowSum[i], colSum[i] 108sum(rowSum) sum(colSum)
方法贪心
思路与算法
给你两个长度为 n 和 m 的非负整数数组 rowSum 和 colSum 其中 rowSum[i] 是二维矩阵中第 i 行元素的和colSum[j] 是第 j 列元素的和。现在我们需要返回任意一个大小为 n×m 并且满足 rowSum 和 colSum 要求的二维非负整数矩阵 matrix。
对于 matrix 的每一个位置 matrix[i][j]0 ≤ i n 且 0 ≤ j m我们将 matrix[i][j] 设为 min{rowSum[i], colSum[j]}然后将 rowSum[i], colSum[j] 同时减去 matrix[i][j] 即可。当遍历完全部位置后matrix 即为一个满足要求的答案矩阵。
上述的构造方法的正确性说明如下
首先我们可以容易得到对于某一个位置 matrix[i][j] 处理完后rowSum[i]colSum[j] 一定不会小于 0。然后我们从第一行开始往最后一行构造因为初始时 ∑i0n\sum_{i0}^n∑i0nrowSum[i] ∑j0m\sum_{j0}^m∑j0mcolSum[j]所以对于第一行显然有 rowSum[0] ≤ ∑j0m\sum_{j0}^m∑j0mcolSum[j]所以通过上述操作一定可以使得 rowSum[0] 0同时满足 colSum[j] ≥ 0 对于 0 ≤ j m 恒成立。然后我们对剩下的 n − 1 行和 m 列做同样的处理。当处理完成后matrix 为一个符合要求的答案矩阵。
在实现的过程中当遍历过程中 rowSum[i] 00 ≤ i n 时因为每一个元素为非负整数所以该行中剩下的元素只能全部为 0同理对于 colSum[j] 00 ≤ j m 时该列中剩下的元素也只能全部为 0。所以我们可以初始化 matrix 为全零矩阵在遍历的过程中一旦存在上述情况则可以直接跳过该行或者列。
代码
class Solution {
public:vectorvectorint restoreMatrix(vectorint rowSum, vectorint colSum) {int n rowSum.size(), m colSum.size();vectorvectorint matrix(n, vectorint(m, 0));int i 0, j 0;while (i n j m) {int v min(rowSum[i], colSum[j]);matrix[i][j] v;rowSum[i] - v;colSum[j] - v;if (rowSum[i] 0) {i;}if (colSum[j] 0) {j;}}return matrix;}
};执行用时40 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗32.5 MB, 在所有 C 提交中击败了56.00%的用户 复杂度分析 时间复杂度O(n×m)其中 n 和 m 分别为数组 rowSum 和 colSum 的长度主要为构造 matrix 结果矩阵的时间开销填充 matrix 的时间复杂度为 O(nm)。 空间复杂度O(1)仅使用常量空间。注意返回的结果数组不计入空间开销。 authorLeetCode-Solution
