具有相等行和列的矩阵

3 回答

• 2

  让我们考虑一维情况：你有一个数字数组，你可以进行单个操作：从数组的一个元素的值中取1并将其添加到其他元素 . 目标是使所有元素与最小的操作相等 . 这里的解决方案很简单：你选择随机的“太大的数字”，然后在随机的“太小”数字中加一个 . 现在让我描述一下这与手头的问题有什么关系 .

  您可以轻松计算每列和每行所需的总和 . 这是矩阵中所有元素的总和除以列数或行数 . 从那时起，您可以计算出哪些行和列需要减少以及哪些 - 增加 . 看这里：

  1 1 2 2 -2
  1 0 1 1 +1
  0 0 1 1 +2
  1 1 1 2 -1
  +1+2-1-2
  Expected sum of a row: 4
  Expected sum of a column: 4
  

  所以现在我们生成两个数组：行中的位移数组： -2,+1,+2,-1 和列中的位移数： +1,+2,-1,-2 . 对于这两个数组，我们解决了上述简单的任务 . 很明显，我们无法以比简单任务所需的步骤更少的步骤解决初始问题（否则列或行中的余额不会为0） .

  但是，我将证明初始任务可以完成与解决列和行任务所需的最大步骤完全相同的步骤来解决：

  更简单的任务中的每一步都会生成两个索引 i 和 j ：要从中减去的索引和要添加的索引 . 让我们假设在列任务的一个步骤中我们有索引 ci 和 cj ，在行任务中我们有索引 ri 和 rj . 然后我们在初始任务中分配一个对应关系：从 (ci, ri) 取1并将一个添加到 (cj, rj) . 在某些时候，我们将达到这样一种情况，其中可能还有更多的步骤，比如列任务，而不再是行任务 . 所以我们得到 ci 和 cj ，但我们如何为 ri 和 rj 做什么？我们只选择 ri = rj ，这样我们就不会搞砸行计算 .

  在这个解决方案中，我正在利用我允许的事实来获得矩阵中的负数 .

  现在让我们演示：

  Solution for columns:
  4->1;3->2;4->2
  Solution for rows:
  1->3;1->3;2->4
  
  Total solution:
  (4,1)->(1,3);(3,1)->(2,3);(4,2)->(2,4)
  

  回复于 2024-04-29T23:12:29+08:00
• 3

  首先，找到每行和每列的预期总和1 .

  rowSum = totalSum / numRows
  colSum = totalSum / numCols
  

  然后，遍历行和列并计算以下值：

  rowDelta = 0
  for each row r
      if sum(r) > rowSum
         rowDelta += sum(r) - rowSum
  
  colDelta = 0
  for each col c
      if sum(c) > colSum
         colDelta += sum(c) - colSum
  

  balancer 所有行和列的最小移动次数为：

  minMoves = max(rowDelta, colDelta)
  

  这是有效的，因为您必须从超过 rowSum 的行转移到不超过它的行，并从超过 colSum 的列转移到不超过它的列 .

  如果最初 rowDelta 低于 colDelta ，那么您将达到 balancer 所有行的阶段，但列仍然没有 balancer . 在这种情况下，您将继续从单元格转移到同一行中的其他单元格 . 如果最初 colDelta 低于 rowDelta ，则同样适用，这就是为什么我们选择它们之间的最大值作为预期结果 .

  1如果totalSum不是numRows或numCols的倍数，则问题无法解决 .

  回复于 2024-04-29T23:12:29+08:00
• 1

  Supose thar r1 是具有最大总和的行的索引，而 r2 是具有最小总和的行 . c1 具有最大总和的列和具有最小值的 c2 列 .

  您需要重复以下操作：

  • if Matrix[r1][c1] == Matrix[r2][c2] 我们完成了！

  • 否则， Matrix[r1][c1] -= 1 和 Matrix[r2][c2] += 1

  回复于 2024-04-29T23:12:29+08:00