c++ - 以最佳方式返回负数的计数

Question

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

给定一个按行和列排序的二维矩阵。您必须以最佳方式返回负数的计数。

我能想到这个解决方案

1. 初始化 rowindex=0

2. 如果行索引>0 行索引++
   否则应用二分查找

并使用此代码实现 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/PIlNd2x 行和 y 列的矩阵的运行时间 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(m+n) 做得更好，但如果您期望负数远少于 m+n，您可能可以获得更好的通常情况时间。

假设您有一个 n x n 数组，其中 array[i][j] < 0比较 i < n-j .在那种情况下，算法可以判断出 array[i][n-1-i] < 0 的唯一方法对于任何我都是通过查看那个单元格。因此，该算法必须至少查看 n 个单元格。