用 Python 编写程序，根据行和列的总和查找有效矩阵

pythonserver side programmingprogramming更新于 2025/11/30 0:44:17

假设我们有两个数组 rowSum 和 colSum，它们具有非负值，其中 rowSum[i] 表示二维矩阵第 i 行元素的总和，colSum[j] 表示第 j 列元素的总和。我们必须找到满足给定 rowSum 和 colSum 值且大小为非负值(rowSum 大小 x colSum 大小)的任何矩阵。

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

9	4	0
0	9	5
0	0	12

为了解决这个问题，我们将遵循以下步骤 −

matrix := create empty矩阵
visited := 一个新集合
定义一个函数 minimum() 。这将需要 r,c
min_total := infinity
type := blank string
对于 i 在 0 到 r - 1 的大小范围内，执行
- 如果 r[i] < min_total，则
  - index := i
  - type := 'row'
  - min_total := r[i]
对于 i 在 0 到 c - 1 的大小范围内，执行
- 如果 c[i] < min_total，则
  - min_total := c[i]
  - type := 'col'
  - index := i
如果 type 与"row"相同，则
- r[index] := infinity
- 对于 i 在 0 到 c - 1 的大小范围内的情况，执行
  - 如果 c[i] 与 infinity 不同且 c[i] >= min_total，则
    - c[i] := c[i] - min_total
    - matrix[index, i] := min_total
    - 退出循环
如果 type 与 'col' 相同，则
- c[index] := infinity
- 对于 i 在 0 到 r - 1 的大小范围内的情况，执行
  - 如果 r[i] 与 infinity 不同且 r[i] >= min_total，则
    - r[i] := r[i] - min_total
    - matrix[i, index] := min_total
    - 退出循环
将对 (index,type) 插入到 accessed
从主方法执行以下操作 −
当 accessed 的大小与 r +len(c) 的大小不同时，请执行
minimum(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))