返回的最佳方式负数的计 [英] Return the count of negative numbers in the optimal way

问题描述

在搜索中的排序按行和纵列矩阵的变化

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.

我觉得这个解决方案

1. 初始化rowIndex位置= 0

1. initialise rowindex=0

如果row​​Index位置> 0 rowIndex位置++
其他应用二进制搜索

if rowindex>0 rowindex++
else apply binary search

和实施与本code为5X5矩阵

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

我跑了code在这里 http://ideone.com/PIlNd2 运行时间为O（xlogy）为x行和y列的矩阵

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

纠正我，如果我错了，在时间复杂度和执行code

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?

推荐答案

O（M + N）的算法，其中m和n是阵列的尺寸，通过滑下负部分的顶部，发现最后工作每行中负数。这是最有可能的是什么PRASHANT是在评论中谈到：

O(m+n) algorithm, where m and n are the dimensions of the array, working by sliding down the top of the negative portion, finding the last negative number in each row. This is most likely what Prashant was talking about in the comments:

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负数少，你可以得到一个更好的通常情况下的时间。

We can't do better than worst-case O(m+n), but if you're expecting far fewer than m+n negative numbers, you may be able to get a better usual-case time.

假设你用N阵列，其中数组[I] [J]其中有一个n; 0 当且仅当 I＆LT; ñ-J 。在这种情况下，只有这样的算法，可以告诉大家，数组[I] [N-1] - ; 0 任何我是看该小区。因此，该算法看至少有N个单元。

Suppose you have an n by n array, where array[i][j] < 0 iff i < n-j. In that case, the only way the algorithm can tell that array[i][n-1-i] < 0 for any i is by looking at that cell. Thus, the algorithm has to look at at least n cells.

这篇关于返回的最佳方式负数的计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！