我正在通过我的大学处理一些有问题的复杂性问题:
程序输入:一个n x n Array[][]被填充以0或1.
定义:如果在行中所有值都是,则定义k为SINK,并且在列中所有值都是(除了本身需要)k0k1[k][k]0
程序输出:是否有一个SINK号码?如果是这样,返回k,否则返回-1.
示例:

在Arr A上,k = 3是SINK,在Arr B上没有SINK,因此返回-1.
这个任务的主要问题是程序的复杂性必须低于O(n^2),我已经设法用这种复杂性解决了这个问题,越过了对行和列求和的斜线.我还没有办法用O(logn)或解决这个问题O(n).此任务还会阻止您使用另一个Array [](由于内存复杂性).任何人都可以放弃这件事吗?提前致谢!