给定行和列的和求可行矩阵【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(nm)O(nm)
    • 空间复杂度：O(1)O(1)O(1)

• 实现：

  自己实现的时候假定了第一个值为0，然后再构造的，有个案例卡住了，然后check了一下，将rowSum和colSum不为0的位置，增大相应值，会出现这样的原因是第一个值取小了，然后就没有假定第一个值为0，通过了。

  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++){if (i == 0 && j == 0){res[i][j] = 0;}else{int mn = Math.min(rowSum[i], colSum[j]);res[i][j] = mn;rowSum[i] -= mn;colSum[j] -= mn;}}}// check for (int i = 0; i < m; i++){if (rowSum[i] != 0){for (int j = 0; j < n; j++){if (colSum[i] != 0){int mn = Math.min(rowSum[i], colSum[j]);res[i][j] += mn;rowSum[i] -= mn;colSum[j] -= mn;}}}}return res;}
  }
  

  • 复杂度
    • 时间复杂度：O(nm)O(nm)O(nm)
    • 空间复杂度：O(1)O(1)O(1)