以最佳方式返回负数的计数

Question

"在矩阵中搜索按行和列排序"的变体

给定按行和列方式排序的2D矩阵.您必须以最佳方式返回负数的计数.

我能想到这个解决方案

1. 初始化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)为x行和y列的矩阵

如果我在时间复杂性或代码实现方面出错,请纠正我

有没有人比这更好的想法来提高运行时复杂性？

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(m + n)做得更好,但是如果你期望远低于m + n的负数,你可能能够获得更好的通常情况时间.

假设你有一个n×n数组,其中array[i][j] < 0iff i < n-j.在这种情况下,算法可以告诉array[i][n-1-i] < 0任何i 的唯一方法是查看该单元格.因此,该算法必须至少查看n个单元.