Lol*_*lly 3 algorithm
我在接受采访时遇到了这个问题.你有一个包含1和0的nxn矩阵.您必须以最有效的方式找到包含最大数量1的行.我知道它可以在n ^ 2中完成但是有没有最佳解决方案呢？
Mar*_*ers 7
最优解是O(n ^ 2).假设矩阵仅包含零.你必须检查每个细胞以确定这一点.这是O(n ^ 2).
你可以优化算法,使它停止搜索,如果它找到一个只包含1的行(这必须是最优的),或者如果它已经连续看到这么多的零,那么它不可能超过目前为止看到的最大值.在某些情况下,这可以显着提高速度,但在一般情况下仍然是O(n ^ 2).
归档时间：
13 年，11 月 前
查看次数：
227 次
最近记录：
13 年，7 月 前