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

  • Z时代
  • 2024-01-10
  • 分类：问答

我遇到了矩阵问题，但正试图找出最佳解决方案。 问题陈述本身就是问题。 进一步见下文给定一个按行排序的布尔矩阵。返回最大数为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。这些都很容易处理，伪代码的重点只是传达一般算法。

回答：

此问题的解决方案取决于每行中元素的数量和列数。 这是一种方法。

第1步： 简单做的所有元素的二进制& &操作中的每一列，直到你得到一个真正的，这意味着我们发现了至少有一个一个的列。这需要最多n个步骤，其中n是列数。

第2步： 现在在该列中搜索一个从上到下的行，给出最大行数。这需要m的steps.where m以下是行 的数量，以便整体需要O（M + N）步

它还可以帮助您找到多行，如果任何具有相同属性

以上是 给定一个按行排序的布尔矩阵。返回最大数为1的行 的全部内容， 来源链接： utcz.com/qa/261603.html

回到顶部