在n*n矩阵中，n<=900，且a(i,j)=0或a(i,j)=1时，如何找到每个a(i,j)的条目？

Question

假设我给了n个基本 n*n 矩阵的开头都是零。

并给出每行每列的相关总和。

例如 n=4

矩阵。

0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0

给定行数和 。2, 2, 1, 1

给定列的和。 2, 0, 2, 2

所以输出矩阵应该是这样的：

0 0 1 1
1 0 0 1
0 0 1 0
1 0 0 0

总有一个解决方案存在。所以对于 n=4, 0<=rowsum<=4 and 0<=columnsum<=4

Answer 1

你可以用一个贪婪的方法来解决这个问题。

while not filled:
    find biggest unfilled row:
        fill in putting 1s in columns with largest sums

在你的情况下，你开始用。

    2 2 0 2
  ----------
2 | _ _ _ _
2 | _ _ _ _
1 | _ _ _ _
1 | _ _ _ _

填入其中一行，我们得到：

    1 1 0 2
  ----------
2 | _ _ _ _
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

填入另一行

      1   1
  ----------
  | 1 0 0 1
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

另外两行也可以用同样的方法填入。

  ----------
  | 1 0 0 1
  | 1 1 0 0
  | 0 1 0 0
  | 0 0 0 1

假设行值的总和和列值的总和一致，然后 0 <= value <= n 对所有的人来说，这个过程总是有效的。

---

更新：正如评论中所指出的那样，没有解决方案有可能以其他方式存在。 这将可以通过以下事实检测到：你试图填入一行，但没有足够的列来填充它。

然而如果你遇到了这样的障碍，那么就没有解决方案。

Answer 2

Btilly的答案会对你有用。然而它还可以改进。你可以通过降序排序来进行预处理，而不是每次都找到最大和的行和列，但重要的是要保持它们的原始位置存储。你可以使用一个简单的类。

class SortedRow {
    int val;
    int originalIndex;
    public SortedRow(val, originalIndex) {
        this.val = val;
        this.originalIndex = originalIndex;
    }
}

然后对它们进行排序(rowVals和colVals是具有所需总和的数组)。

public static void preprocess(int[] rowVals, int[] colVals){
    SortedRow[] rows = new SortedRow[n];
    SortedRow[] cols = new SortedRow[n];
    for (int i = 0; i < n; i++) {
        rows[i] = new SortedRow(rowVals[i], i);
        cols[i] = new SortedRow(colVals[i], i);
    }
    // Sort both arrays by val with some sorting algorithm of your choice - in descending order!
}

现在你可以像Btilly建议的那样 用贪婪的方法来填充一个nxn矩阵 除了你不必每次都去找最大的那个--你已经有了它。通过以下方式来填充它 originalIndex 领域的新类。

它将最坏情况下的运行时间从三次方改进为二次方。预处理的运行时间是O(nlogn), 如果你有一些事先的知识，甚至可以是线性的。n. 填写矩阵的运行时间为O(n^2)。