在Python中查找给定行和列总和的有效矩阵的程序

假设我们有两个非负值数组rowSum和colSum，其中rowSum[i]具有第i行元素的总和，colSum[j]具有第j列元素在2D矩阵中的总和。我们必须找到任何大小为（rowSum size x colSum size）的非负值矩阵，该矩阵满足给定的rowSum和colSum值。

因此，如果输入为rowSum = [13,14,12] colSum = [9,13,17]，则输出将为

9	4	0
0	9	5
0	0	12

要解决这个问题，我们将按以下步骤进行−

矩阵：= 创建空矩阵
visited：=新集合
定义函数minimum() 。这将采取r，c
min_total：= infinity
类型：=空白字符串
对于范围在0到r大小-1的i，执行以下操作：
- 如果r[i]＜min_total，则
  - index：= i
  - 类型：=“行”
  - min_total：= r[i]
对于范围在0到c大小-1的i，执行以下操作：
- 如果c[i]＜min_total，则
  - min_total：= c[i]
  - 类型：=“列”
  - index：= i
如果类型与“行”相同，则
- r[index]：= infinity
- 对于范围为0到c大小-1的i，执行以下操作：
  - 如果c[i]与无穷大不同且c[i]≥min_total，则
  - c[i]：= c[i] – min_total
  - matrix[index，i]：= min_total
  - 退出循环
如果类型与“列”相同，则
- c[index]：= infinity
- 对于范围为0到r大小-1的i，执行以下操作：
  - 如果r[i]与无穷大不同且r[i]≥min_total，则
  - r[i]：= r[i] – min_total
  - matrix[i，index]：= min_total
  - 退出循环
将对（index，type）的插入放入visited中
从main方法执行以下操作−
while已访问的大小与r+len(c)的大小不同，则
最小值（r，c）
返回matrix

示例

让我们看看以下实现以获得更好的理解−

def solve(r, c):
   matrix = [[0]*len(c) for _ in range(len(r))]
   visited = set()

   def minimum(r,c):
      min_total = float('inf')
   
      type = ''
      for i in range(len(r)):
         if(r[i]＜min_total):
            index = i
            type = 'row'
            min_total = r[i]

      for i in range(len(c)):
         if(c[i]＜min_total):
            min_total = c[i]
            type = 'col'
            index = i

      if(type == 'row'):
         r[index] = float('inf')

         for i in range(len(c)):
            if(c[i] != float('inf') and c[i] ≥ min_total):
               c[i] -= min_total
               matrix[index][i] = min_total
               break

      if(type == 'col'):
         c[index] = float('inf')
         for i in range(len(r)):
            if(r[i] != float('inf') and r[i] ≥ min_total):
               r[i] -= min_total
               matrix[i][index] = min_total
               break

      visited.add((index,type))

   while len(visited) != len(r)+len(c):
      minimum(r,c)

   return matrix

rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))