3

一个二维矩阵用 1 和 0 填充。假设连续的所有 1 都在所有 0 之前。我们必须找到连续 1 的最大数量。

我已经提出了解决方案，我们可以在每一行上应用二进制搜索，以在 0 开始之前获取该行中最后一个 1 的最后一个索引，因此没有。1的将是它的索引+1。所以我们可以在每一行都这样做。所以复杂度将是 O(mlogn)，其中 m 是数字。行数，n 是行数。的列。可以有更好的解决方案吗？

4

7 回答 7

3

您只对最大值感兴趣，因此您不必为每一行找到开关的位置。

找到第一行的开关位置k(0)后，从位置k(0)开始搜索第二行，如果是0，那么第二行不包含最长的序列，所以可以忽略where它实际上是。这不会提高最坏情况的时间复杂度，但会提高平均情况。

于 2012-04-07T13:03:52.217 回答
3

它可以在O（n + m）中完成。

从等于 0 的 curmax 开始。

然后逐行处理。当该行中至少有 curmax 时增加 curmax，即检查 curmax 值是否为 1。

在处理完所有行之后，答案将是 curmax-th。

这将在 O(n+m) 中工作。

它会比 O(m*logn) 快吗？这取决于。如果 m 小于 n/(log(n) - 1) 它将起作用，实际上比 O(m*log n) 更长，否则更快，仅就复杂性而言。
在估算时间时，考虑常数是另一个问题。所以对于一个数量级的 n 和 m 这会更快，对于不同的只有一个选择 - 尝试两者，选择更好。

于 2012-04-07T13:11:26.173 回答
3

O(n+m) 算法的要点是这样的。

把你的矩阵想象成一个网格。

从左上角开始。

如果你在 1，向右移动。否则向下移动。

继续这样做，直到通过最后一行。

那么你的 x 坐标是 1 的最大计数。

如果有一行全为 1，您可以将其移过最后一列。您的算法需要满足这一点。

于 2012-04-07T13:21:48.943 回答
1 
1     bool matrix[100][200];
2     int max = 0, count, x;
3     
4     for(int y=0;y<100;y++){
5         count = 0;
6         x=max; // This would optimize the search times!
7         for(;x<200;x++){
8             if(matrix[y][x] == 0 && count>max){
9                max=count;
10            }
11            else count++;
12        }
13        if(x == 199)break; // Optimization - the end reached
14    }
15
16    // Now the max var contains the maximum number of 1's of a single row in all columns.

无需遍历每一行，您只需跳过已知位置即可。这种优化在第 6 行实现。

于 2012-04-07T13:15:25.780 回答
0

只需连续检查它，然后从您在上一行停止的位置开始下一行。如果为 0，则转到下一行，否则继续检查该行。重复该过程直到最后一行。

于 2012-04-07T13:08:18.123 回答
0

似乎在上面的代码中，第 5 行，即 count = 0 应该从第一个循环中出来，因为如果最大数量的 1 不在矩阵的第一行中，它会错误地更新 max 变量。

我在下面编写的正确测试代码：

public static int findRowWithMax1s(int arr[][],int m, int n){

    int x,y,count=0,max=0;
    int row = 0;
    for(x=0;x<m;x++) {
        y = max;
        for(;y<n;y++) {
            if(arr[x][y] == 0) {
                max = count;
                row = x;
                break;
            }
            else
                count++;
        }
    }

    return max;
}
于 2015-04-09T16:26:22.637 回答
0 
#include <stdio.h>
#define R 4
#define C 4

/* A function to find the index of first index of 1 in a boolean array arr[] */
int first(bool arr[], int low, int high)
{
  if(high >= low)
  {
    // get the middle index  
    int mid = low + (high - low)/2; 

    // check if the element at middle index is first 1
    if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
      return mid;

    // if the element is 0, recur for right side
    else if (arr[mid] == 0)
      return first(arr, (mid + 1), high);

    else // If element is not first 1, recur for left side
      return first(arr, low, (mid -1));
  }
  return -1;
}

// The main function that returns index of row with maximum number of 1s. 
int rowWithMax1s(bool mat[R][C])
{
    int max_row_index = 0, max = -1; // Initialize max values

    // Traverse for each row and count number of 1s by finding the index 
    // of first 1
    int i, index;
    for (i = 0; i < R; i++)
    {
       index = first (mat[i], 0, C-1);
       if (index != -1 && C-index > max)
       {
           max = C - index;
           max_row_index = i;
       }
    }

    return max_row_index;
}

/* Driver program to test above functions */
int main()
{
    bool mat[R][C] = { {0, 0, 0, 1},
        {0, 1, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0}
    };

    printf("Index of row with maximum 1s is %d n", rowWithMax1s(mat));

    return 0;
}
于 2017-07-08T02:55:36.263 回答