Java / C# - Array[][]复杂性任务
提问于 2013-11-29 02:06:12
我正在通过我的大学处理一些有问题的复杂问题：
程序输入:一个n x n Array[][]，由0或1填充。
定义:将k定义为接收器，如果在k行中所有的值都是0，而在k列中所有的值都是1 (需要0的[k][k]本身除外)
程序输出:是否有一个k号是接收器？如果是，则返回k，否则返回-1。
例子：
在Arr A上，k=3是一个接收器，在Arr B上没有接收器，所以1被返回.
这个任务的主要问题是程序的复杂性必须低于O(n^2)，我已经设法用这种复杂性解决了这个问题，遍历了行和列的斜线之和。我还没有找到用O(logn)或O(n)解决这个问题的方法。此外，该任务还防止您使用另一个数组Due to memory complexity。有人能对那件事略知一二吗？提前谢谢！
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-11-29 03:52:08
为了明确哈罗德在OP评论中的答案:首先列出所有n索引，S = {0, 1, .., n-1}。这些是我们的水槽的候选。在每一步，我们都要消除其中的一个。
- 考虑
S的前两个元素，比如i和j。 - 检查
A[i, j]是否为1.- 如果是，从S中删除
i(因为I行不是全部为0，所以i不能作为我们的接收器) - 如果不是，从S中删除
j(因为j列不是全部是1s，所以j不能作为我们的接收器)
- 如果是，从S中删除
- 如果S中还有两个或多个元素，请返回到步骤1。
- 当我们到最后一个元素时，比如
k，检查第k行是否都是零，k列(A[k,k]除外)是否都是零。- 如果它们是，
k是一个接收器，您可以返回它。 - 如果不是，矩阵就没有接收器，您可以返回
-1。
- 如果它们是，
首先，在n中有S元素，每一步都消除其中的一步，每一步都要花费恒定的时间，所以总体上是O(n)。
你提到你不想使用第二个数组。如果这是严格的，你可以用两个整数来代替，一个代表最后一步的“幸存者”，另一个代表序列0，1，…，n-1的距离。
我以前从未见过这种算法，它的简单给我留下了深刻的印象。干杯。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20283150
复制相关文章
![html遮罩层动画制作,flash简单制作遮罩动画效果[通俗易懂]](https://ask.qcloudimg.com/http-save/yehe-8223537/f77026741bf2c73be07071b98c26ed73.gif)
腾讯云开发者
