给定行和列的和求可行矩阵【LC1605】
给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。
换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。
早起了一天 还不错
- 思路：
从左上角开始逐行或者逐列构造，由于要求构造的每个值大于等于0，因此每次能够构造的值是rowSum和colSum的最小值【贪心】，构造完毕后将rowSum和colSum减小相应的值，然后再继续构造 - 实现
class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int m = rowSum.length, n = colSum.length; int[][] res = new int[m][n]; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ int mn = Math.min(rowSum[i], colSum[j]); res[i][j] = mn; rowSum[i] -= mn; colSum[j] -= mn; } } return res; } }
复杂度
- 时间复杂度：O(nm)
- 空间复杂度：O(1)
