Мы должны найти строку, которая имеет максимальное количество единиц в матрице, отсортированной по строкам. Предположим, что R представляет собой номер строки, а C представляет номер столбца в матрице.

Мы решим это за O (R * C), O (R * log (C)) и O (R + C) временную сложность.

Пример-

Я собираюсь объяснить его решение с временной сложностью O (R * C), O (R * log (C)) и O (R + C).

O (R * C) Решение

Это простое решение методом грубой силы, в котором мы будем проходить через каждую строку и считать 1. При подсчете мы продолжаем отслеживать максимум 1 в строке.

Программа C ++:

#include<iostream>
using namespace std;
int main(){
 int R,C,ans=0,row;
 R = 3;
 C = 4;
 int mat[3][4] = {{0,0,0,1},{0,1,1,1},{0,0,0,0}};
for(int i=0; i<R; i++){
        int count = 0;
        for(int j=0; j<C; j++){
           if(mat[i][j]==1)
           count++;
        }
        if(ans<count)
        {
          ans = count;
          row = i;
        }
 }
 cout<<row<<endl;
}

O (R * log (C)) Решение

Поскольку каждая строка отсортирована, вместо проверки каждого элемента мы можем выполнить поиск по индексу самого левого вхождения 1, используя двоичный поиск в журнале (C).

Шаг 1. Пройдите через каждый ряд.

Шаг 2. Найдите индекс крайнего левого вхождения 1 с помощью двоичного поиска и вычислите число 1.

Шаг 3. Следите за максимальным количеством единиц и строк.

Вот моя реализация подхода к двоичному поиску на C ++. Пожалуйста, попробуйте реализовать самостоятельно и поделитесь своим кодом. Я хотел бы увидеть вашу реализацию.

Программа C ++:

#include<bits/stdc++.h>
using namespace std;
int main()
{ 
        int R,C;
        int i,j,k,f,x,y;
        cin>>R>>C;
        int a[R][C];
       //Taking matrix as input.
        for(i=0; i<R; i++)
        {
            for(j=0; j<C; j++)
            {
                 cin>>a[i][j];
            }
        }
        j=0;
        k=C-1; 
        f=1;
        int ans,min=INT_MAX;
        for(i=0; i<R; i++)
        {
            j=0;
            k=C-1;
             //Binary Search
            while(k-j>=2)
           {    f=1;
               int mid = j+(k-j)/2;
               if(a[i][mid]==1 && (mid==0 || a[i][mid-1]==0))
               {
                   f=0;
                   x=mid;
                   y=i;
                   break;
               }
               
               if(a[i][mid]==1)
               {
                   k = mid-1;
               }
               else
               {
                  j = mid+1; 
               }
           }
           if(f)
           {
               if(a[i][j]==1)
               x = j;
               else
               x = k;
           }
          
           if(x<min)
           {
               min=x;
               ans=i;
           }
        }
        cout<<ans<<endl;
    }

O (R + C) Лучший подход:

Начните с правой стороны 1-й строки (индекс C-1), пока значение равно 1, продолжайте перемещаться влево. Если в следующей строке меньше 1, игнорируйте ее и отслеживайте максимум 1 строку. Вот наглядное изображение этого алгоритма.

Программа C ++:

#include <bits/stdc++.h>
using namespace std;
int main() {
 int R,C,i,j,row;
 cin>>R>>C;
 int a[R][C];
     for( i=0; i<R; i++) 
     for( j=0; j<C; j++)
     cin>>a[i][j];
     row = 0;
        i = 0;
        j = C - 1;
      while(i < R && j >= 0){
        if(a[i][j] == 1){
            row = i;
            j--;
        }
        else i++;
      }
    cout<<row<<endl;
 return 0;
}