, нахождение максимального числа 1 в строке

Question

2-я матрица задана заполненной 1 и 0. Дано, что все 1 в ряд идут до всех 0. Мы должны найти максимальное число 1 в строке.

Я решил, что мы можем применить бинарный поиск по каждой строке, чтобы получить последний индекс последнего 1 в этой строке до начала 0 и, следовательно, нет. из 1 будет его индекс + 1. Поэтому мы можем делать это в каждом ряду. Таким образом, сложностью будет O (mlogn), где m - нет. строк, а n - нет. столбцов. Может ли быть лучшее решение?

Answer 1

Это может быть сделано в O (n + m).

Начать с curmax равным 0.

Тогда процесс рядов один за другим. Увеличьте curmax, пока в этой строке есть по крайней мере curmax, т. Е. Проверяет, является ли значение curmax равным единице.

Ответ будет curmax-th, после того как все строки обработаны.

Это будет работать в O (n + m).

Будет ли это быстрее, чем O (m * logn)? Это зависит. Если m меньше, чем n/(log (n) - 1), он будет работать, на самом деле дольше, чем O (m * log n), и быстрее, иначе, с точки зрения сложности.
Рассмотрение констант - еще одна проблема при приближении времени. Так что для n и m одной величины это будет быстрее, для разных есть только один выбор - попробуйте оба, выбирайте лучше.

Answer 2

Вас интересует только макс, поэтому вам не нужно находить положение переключателя для каждой строки.

После того, как положение переключателя первой строки найдено k (0), вы просматриваете вторую строку, начиная с позиции k (0), а если она равна 0, то вторая строка не содержит самую длинную последовательность, поэтому вы можете игнорировать, где это на самом деле. Это не улучшает худшую временную сложность, но это улучшит средний случай.

Answer 3

Просто проверьте его в строке и начните в следующей строке с позиции, в которой вы остановились в предыдущей строке. Если его значение 0, перейдите к следующей строке, продолжите проверку строки. Повторите процедуру до последней строки.

Answer 4

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.

Answer 5

Суть алгоритма O (n + m) заключается в следующем.

Представьте свою матрицу в виде сетки.

Начало в верхнем левом углу.

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

Продолжайте делать это, пока не пройдете последний ряд.

Тогда ваша координата x является максимальным числом 1.

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

Answer 6

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

Правильное тестирование кода я написал ниже:

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; 
} 

Answer 7

#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; 
}