• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

给定一个按行排序的布尔矩阵。返回最大数为1的行

arrays 来源:roger_that 11次浏览

我遇到了矩阵问题,但正试图找出最佳解决方案。 问题陈述本身就是问题。 进一步见下文给定一个按行排序的布尔矩阵。返回最大数为1的行

Example 
Input matrix 

    0 1 1 1 
    0 0 1 1 
    1 1 1 1 // this row has maximum 1s 
    0 0 0 0 

Output: 2 

我的解决方案:既然对行进行排序,我想用1中第一次出现的每一行在执行二进制搜索的,再算上1将total number of columns minus index of 1st 1

这将在O(m*logn),但我很想知道逻辑,如果这可以在线性时间完成。

谢谢!


===========解决方案如下:

在右上角开始光标。在每一行中,直到你到达行中的最后一个为止。然后下台。如果你下来,光标指向0,再次下台。永远不要去。您正在寻找距离左侧最远的一排,因此您无需向右看。运行时间为O(n + m),因为您每走一遍,降低m次,最多只剩下n步。下面是一些伪代码,假设矩阵是一个列表的列表:

bestrow = 0 
leftmost = matrix.width 

for i = matrix.height to 0: 
    row = matrix[i] 
    while row[leftmost - 1] == 1: 
     leftmost-- 
     bestrow = i 

return bestrow 

如果直译的代码,你可以有全0矩阵的问题,或者某些行有全1。这些都很容易处理,伪代码的重点只是传达一般算法。


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)