c - 设计一个 O(N) 算法找到 1's from a 2D matrix[N][N] containing 1' s 和 0 的数量

Question

假设二维 [n][n] 矩阵仅包含 1 和 0。任何行中的所有 1 都应位于 0 之前。任何行 i 中 1 的数量应该至少是 1 的行 (i+1) 中的第 no 个。找一个方法，写一个c程序，统计一个二维矩阵中1的个数。算法的复杂度应该是O(n)。

问题来自Cormen的算法书，下面是我对这个问题的实现。请指出我算法中的错误和/或建议更好的方法。谢谢!

#include <stdio.h>
#include <stdlib.h>

int **map;
int getMatrix();

main()
{
    int n,i,j,t;
    j=0;
    n=getMatrix();
    i=n-1;  
    int sum[n];
    for(t=0;t<n;t++)
        sum[t]=0;
    int count=0; 
    while ( (i>=0) && (j<n) )
    {
        if ( map[i][j] == 1 )
        {
            j++;
            count=count+1;
        }
        else
        {
            if (i==(n-1))
            {
                sum[i]=count;
                count=0;
                            i--;
            }   
            else            
            {
                sum[i]=sum[i+1]+count;
                count=0;            
                i--;
            }
        }
    }
    for (t=0;t<n;t++)
    { 
        if ((t==(n-1)) && (sum[t]==0))
            sum[t]=0;
        else if ((sum[t]==0) && (sum[t+1]>0))  
            sum[t]=sum[t+1];
    }
    int s=0;
    for (t=0;t<n;t++)
        s=s+sum[t];
    printf("\nThe No of 1's in the given matrix is %d \n" ,s);
}

int getMatrix()
{
    FILE *input=fopen("matrix.txt","r");
    char c;
    int nVer=0,i,j;
    while((c=getc(input))!='\n')
        if(c>='0' && c<='9')
            nVer++;
    map=malloc(nVer*sizeof(int*));
    rewind(input);
    for(i=0;i<nVer;i++)
    {
        map[i]=malloc(nVer*sizeof(int));
        for(j=0;j<nVer;j++)
        {
            do
            {
                c=getc(input);
            }while(!(c>='0' && c<='9'));                  
            map[i][j]=c-'0';
        } 
    }
    fclose(input);
    return nVer;
} 

Answer 1

当你首先描述你想做什么时，更容易发现问题。 无论如何，在我看来你有一个问题，你设置

i == (n-1), 在初始化阶段，如果 statmnet 是正确的并且你没有减少 i，每次你输入这个，

if (i==(n-1))
                {
                sum[i]=count;
                count=0;

                **i--;**
            }   
            else            
            {
                sum[i]=sum[i+1]+count;
                count=0;            
                i--;
            }