<分区>
我正在通过我的大学处理一些有问题的复杂性问题:
程序输入:n x n Array[][]，其中填充有 0 或 1。
定义:如果 k 行中的所有值都是 0，则将 k 定义为 SINK，并且在 k 列中，所有值都是 1([k][k] 本身除外，它需要为 0)
程序输出:是否有第 k 个数是 SINK？如果是，返回k，否则返回-1。
示例:
在 Arr A 上 k=3 是一个 SINK，在 Arr B 上没有 SINK，所以返回 -1。
这个任务的主要问题是程序的复杂度必须低于 O(n^2) ，我已经设法解决了这个问题，通过斜线求和行和列。我还没有找到用 O(logn) 或 O(n) 解决这个问题的方法。该任务还阻止您使用另一个 Array[] (由于内存复杂性)。任何人都可以对此事有所了解吗？提前致谢!
最佳答案
只是为了明确哈罗德在 OP 的评论中链接到的答案:从所有 n 索引的列表开始，S = {0, 1, .., n- 1}。这些是我们的水槽候选者。在每一步，我们都将消除其中一个。
S 的前两个元素，比如 i 和 j。A[i, j] 是否为 1。
i(因为第 i 行不全为 0，所以 i 不能我们的水槽)j(因为第 j 列不全为 1，所以 j 不能'不是我们的水槽)k，检查第 k 行是否全为零以及第 k 列 (除了 A[k,k]) 都是 1。
k 就是一个接收器，您可以返回它。 -1。S 中有 n 个元素开始，每一步消除一个元素，每一步都需要常数时间，所以 O(n) 总体而言。
您提到您不想使用第二个数组。如果这真的很严格，你可以只使用两个整数，一个代表最后一步的“幸存者”，一个代表你进入序列 0, 1, .., n-1 的距离是。
我以前从未见过这种算法，它的简单性给我留下了深刻的印象。干杯。
关于c# - Java/C# - Array[][] 复杂性任务，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20283150/