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 次檢視

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告