Python程序：根据行和列的总和查找有效的矩阵

假设我们有两个数组 `rowSum` 和 `colSum`，它们包含非负值，其中 `rowSum[i]` 包含第 i 行元素的总和，`colSum[j]` 包含第 j 列元素的总和。我们需要找到一个大小为 ( `rowSum` 大小 x `colSum` 大小) 的具有非负值的矩阵，以满足给定的 `rowSum` 和 `colSum` 值。

因此，如果输入类似于 `rowSum = [13,14,12]`，`colSum = [9,13,17]`，则输出将是……

940
095
0012

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

  • matrix := 创建一个空矩阵
  • visited := 一个新的集合
  • 定义一个函数 `minimum()`。它将接收 r, c 作为参数。
  • min_total := 无穷大
  • type := 空字符串
  • 对于范围从 0 到 r 的大小 - 1 的 i，执行：
    • 如果 r[i] < min_total，则：
      • index := i
      • type := 'row'
      • min_total := r[i]
  • 对于范围从 0 到 c 的大小 - 1 的 i，执行：
    • 如果 c[i] < min_total，则：
      • min_total := c[i]
      • type := 'col'
      • index := i
  • 如果 type 等于 'row'，则：
    • r[index] := 无穷大
    • 对于范围从 0 到 c 的大小 - 1 的 i，执行：
      • 如果 c[i] 不等于无穷大且 c[i] >= min_total，则：
        • c[i] := c[i] - min_total
        • matrix[index, i] := min_total
        • 跳出循环
  • 如果 type 等于 'col'，则：
    • c[index] := 无穷大
    • 对于范围从 0 到 r 的大小 - 1 的 i，执行：
      • 如果 r[i] 不等于无穷大且 r[i] >= min_total，则：
        • r[i] := r[i] - min_total
        • matrix[i, index] := min_total
        • 跳出循环
  • 将 (index, type) 对插入 visited
  • 在主方法中执行以下操作：
  • 当 visited 的大小不等于 r 的大小 + 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))

输入

[13,14,12], [9,13,17]

输出

[[9, 4, 0], [0, 9, 5], [0, 0, 12]]

更新于：2021年10月4日

249 次查看

开启您的职业生涯

通过完成课程获得认证

开始学习
广告