Какая строка имеет наибольшее 1 с в матрице 0-1 со всеми 1 с "слева"?

Question

Задача

Каждая строка матрицы nxn состоит из 1 и 0, так что в любой строке все 1 идут перед любыми 0.Найти строку, содержащую большинство из 1 в O (n).

Пример

1 1 1 1 1 0  <- Contains maximum number of 1s, return index 1
1 1 1 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
1 1 0 0 0 0

Я нашел этот вопрос в своей книге алгоритмов.Лучшее, что я мог сделать, заняло O (n logn) время.Как это сделать в O (n)?

Answer 1

Начните с 1,1.

Если в ячейке 1, то вы находитесь в самой длинной строке; запишите это и идите направо. Если ячейка содержит 0, спуститесь вниз. Если ячейка выходит за границы, все готово.

Answer 2

Вы можете сделать это в O(N) следующим образом:

Начать с A[i][j] с i=j=0.

          1, keep moving to the right by doing j++
A[i][j] = 
          0, move down to the next row by doing i++

Когда вы достигнете последней строки или последнего столбца,ответом будет значение j.

Псевдокод:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = 0   
Let max1Row = 0

while ( i<R && j<C )
   if ( matrix[i][j] == 1 )
      j++
      max1Row = i
   else
      i++
end-while


print "Max 1's = j"
print "Row number with max 1's = max1Row"

Answer 3

Начните с первого ряда.Сохраните строку R, которая имеет наибольшее число 1 и индекс i последней 1 из R.в каждой итерации сравнивайте текущую строку со строкой R по индексу i.если текущая строка имеет 0 в позиции i, строка R по-прежнему является ответом.В противном случае верните индекс текущей строки.Теперь нам просто нужно найти последнюю 1 из текущей строки.Выполните итерацию от индекса i до последней 1 текущей строки, установите R для этой строки и i для этого нового индекса.

              i
              |  
              v 
R->   1 1 1 1 1 0  
|
v     1 1 1 0 0 0 (Compare ith index of this row)
      1 0 0 0 0 0         Repeat
      1 1 1 1 0 0           "
      1 1 1 1 0 0           "
      1 1 0 0 0 0           "

Answer 4

int [] getMax1withRow(int [][] matrix){
    int [] result=new int[2];
    int rows=matrix.length;
    int cols=matrix[0].length;
    int i=0, j=0;
    int max_row=0;// This will show row with maximum 1. Intialing pointing to 0th row.
    int max_one=0;// max one
    while(i< rows){
        while(matrix[i][j]==1){
            j++;
        }
        if(j==n){
             result[0]=n;
             result[1]=i;
             return result;
        }
        if(j>max_one){
             max_one=j;
             max_row=i;
        }
        j=0;// Again start from the first column
        i++;// increase row number
    }
    result[0]=max_one;
    result[1]=max_row;
    return result;
}

Сложность по времени => O (строка + столбец), в худшем случае, если в каждой строке есть n-1, кроме последней строки, в которой есть n 1s, то мы должны пройти до последней строки.

Answer 5

Некоторый C-код для этого.

int n = 6;
int maxones = 0, maxrow = -1, row = 0, col = 0;
while(row < n) {
    while(col < n && matrix[row][col] == 1) col++;
    if(col == n) return row;
    if(col > maxones){
        maxrow = row;
        maxones = col;
    }
    row++;
}