Мы должны найти строку, которая имеет максимальное количество единиц в матрице, отсортированной по строкам. Предположим, что 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; }