3

A variation of "Searching in a Matrix that is sorted rowwise and columnwise"

Given a 2D Matrix that is sorted rowwise and columnwise. You have to return the count of negative numbers in most optimal way.

I could think of this solution

  1. initialise rowindex=0

  2. if rowindex>0 rowindex++
    else apply binary search

And implemented in with this code for 5X5 matrix

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

I ran the code here http://ideone.com/PIlNd2 runtime O(xlogy) for a matrix of x rows and y columns

Correct me if i am wrong in time complexity or implementation of code

Does anyone have any better idea than this to improve Run-time complexity?

4

2 回答 2

7

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 个单元格。

于 2013-07-21T19:32:13.320 回答
0

您正在执行二进制搜索。因此，您将 n 除以 2 以找到中点，然后继续除以，然后返回一个值。即使您为每一行划分列，这看起来也像二进制搜索。因此，您正在执行 O(log n)。或者像 O(x log n/y) 这样的东西。

于 2013-07-22T00:13:25.097 回答