Возвращает количество отрицательных чисел в оптимальном пути

Question

Разновидности «Поиск в матрице, которая сортируется построчно и столбцы»

Данного 2D-матрица, которая сортируется построчно и столбцы. Вы должны вернуть счет отрицательных чисел наиболее оптимальным способом.

я мог думать об этом решении

1. Initialise RowIndex = 0

2. если RowIndex> 0 RowIndex ++
   еще применить бинарный поиск

и реализован с использованием этого кода для матрицы 5X5

#include<iostream> 
#include<cstdio> 
using namespace std; 
int arr[5][5]; 

int func(int row) 
{ 
    int hi=4; 
    int lo=0; 
    int mid=(lo+hi)/2; 
    while(hi>=lo) 
    { 
     mid=(lo+hi)/2; 
     . 
     if(mid==4) 
     { 
      return 5; 
     } 
     if(arr[row][mid]<0 && arr[row][mid+1]<0) 
     { 
      lo=mid+1; 
     } 
     else if(arr[row][mid]>0 && arr[row][mid+1]>0) 
     { 
      hi=mid-1; 
     } 
     else if(arr[row][mid]<0 && arr[row][mid+1]>0) 
     { 
      return mid+1; 
     } 
    } 
} 

int main() 
{ 
    int ri,ci,sum; 
    ri=0; //rowindex 
    ci=0; //columnindex 
    sum=0; 
    for(int i=0; i<5; i++) 
    { 
     for(int j=0; j<5; j++) 
     { 
      cin>>arr[i][j]; 
     } 
    } 
    while(ri<5) 
    { 
     if(arr[ri][ci]>=0) 
     { 
      ri++; 
     } 
     else if(arr[ri][ci]<0) 
     { 
      int p=func(ri); 
      sum+=p; 
      ri++; 
     } 
    } 
    printf("%d\n",sum); 
} 

Я побежал код здесь http://ideone.com/PIlNd2 выполнения O (xlogy) для матрицы х строк и у столбцов

Поправьте меня, если я ошибаюсь, во временной сложности или реализации кода

Есть ли у кого-либо лучшая идея, чем это, для улучшения сложности во время выполнения?

Answer 1

O (m + n) алгоритм, где m и n - размеры массива, работающие путем скольжения вниз по верхней части отрицательной части, нахождение последнего отрицательного числа в каждой строке. Это наиболее вероятно, что Prashant говорил в комментариях:

int negativeCount(int m, int n, int **array) { 
    // array is a pointer to m pointers to n ints each. 
    int count = 0; 
    int j = n-1; 
    for (int i = 0, i < m; i++) { 
     // Find the last negative number in row i, starting from the index of 
     // the last negative number in row i-1 (or from n-1 when i==0). 
     while (j >= 0 && array[i][j] >= 0) { 
      j--; 
     } 
     if (j < 0) { 
      return count; 
     } 
     count += j+1; 
    } 
    return count; 
} 

Мы не можем сделать лучше, чем в худшем случае O (т + п), но если вы ждете гораздо меньше, чем т + п отрицательна чисел, вы можете получить лучшее время обычного случая.

Предположим, у вас есть массив n на n, где array[i][j] < 0 iff i < n-j. В этом случае единственный способ, которым алгоритм может сказать, что array[i][n-1-i] < 0 для любого i, - это посмотреть на эту ячейку. Таким образом, алгоритм должен искать по крайней мере n ячеек.

Answer 2

Вы проводите двоичный поиск. В результате вы делите n на 2, чтобы найти среднюю точку, затем продолжайте делить, прежде чем возвращать значение. Это похоже на двоичный поиск, даже если вы разделите столбцы для каждой строки. Поэтому вы выполняете O (log n). Или что-то вроде O (x log n/y).