c - 设计一个 O(N) 算法，从包含 1 和 0 的 2D 矩阵[N][N] 中找出没有 1

Question

假设一个二维[n][n]矩阵只包含 1 和 0。任何一行中的所有 1 都应该在 0 之前。任何行中 1 的数量i至少应为 1 行中的第 1 行(i+1)。找到一种方法并编写 ac 程序来计算 2D 矩阵中 1 的个数。算法的复杂度应该是 O(n)。

这个问题来自 Cormen's Algorithm Book，下面是我对这个问题的实现。请指出我算法中的错误和/或提出更好的方法。谢谢！

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