3

我遇到了矩阵问题，但试图找出最佳解决方案。问题陈述是问题主题本身。进一步见下文

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)，但我很想知道是否可以在线性时间内完成逻辑。

谢谢！

4

2 回答 2

8

在右上角开始一个光标。在每一行中，向左走，直到到达该行的最后一个 1。然后下台。如果你降级并且光标指向 0，则再次降级。永远不要向右走。您正在寻找最左侧为 1 的行，因此您永远不需要向右看。运行时间为 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 的问题。这些很容易处理，伪代码的重点只是传达通用算法。

于 2013-07-26T05:28:31.340 回答
0

The solution for this problem depends on the number of elements in each row and the number of columns. Here is an approach.

Step 1: Simple do a binary && operation on all elements in each column until you get a true which means we found a column which has at least one one. This take max n steps where n is number of columns.

Step 2: Now do a search for one from top to bottom in that column which gives you the row with max number of ones. This takes max of m steps.where m is number of rows So overall it takes O(m+n) steps

It also helps you find multiple rows if any with the same property

于 2013-07-26T05:52:31.220 回答