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

Ответ 1

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

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

Ответ 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 = j"
print "Row number with max 1 = max1Row"

Ответ 3

Начните с первой строки. Сохраните строку R, которая имеет наибольшее количество 1s и индекс я последнего 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           "

Ответ 4

Некоторые 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++;
}

Ответ 5

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 (строка + col), в худшем случае Если каждая строка имеет n-1 за исключением последней строки, которая имеет n 1s, то мы проезжаем до последней строки.