制定一个O（N）算法发现没有1的从二维矩阵[N] [N]含1和0 [英] devise an O(N) algorithm finding No of 1's from a 2D matrix[N][N] containing 1's and 0's
问题描述
假设一个2D [N] [N] 矩阵containint只有1和0。所有1的在任何行应来之前0。 1在任何行数我至少应为无，1的行（I + 1）。找到一种方法，写C程序计数不为1的在二维矩阵。该算法的复杂度应为O（n）。
现在的问题是，从Cormen的算法书，以下是我实现了这个问题。请指出错误，在我的算法和/或可能提出一个更好的办法。谢谢！
的#include＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
INT **地图;
INT getMatrix（）;
主要（）
{
INT N，I，J，T;
J = 0;
N = getMatrix（）;
I = N-1;
INT总和[N];
对于（T = 0; T＆n种;吨++）
总和[吨] = 0;
诠释计数= 0;
而（（ⅰ＆GT; = 0）及及（J＆n种））
{
如果（图[I] [J] == 1）
{
J ++;
数=计数+ 1;
}
其他
{
如果（ⅰ==第（n-1））
{
总和[我] =计数;
计数= 0;
一世 - ;
}
其他
{
总和[I] =总和[1 + 1] +计数;
计数= 0;
一世 - ;
}
}
}
对于（T = 0; T＆n种;吨++）
{
如果（（T = =（N-1））及及（总和[T] == 0））
总和[吨] = 0;
否则，如果（（总和[T] == 0）及及（总和[T + 1] 0））
总和[T] =总和[T + 1];
}
INT S = 0;
对于（T = 0; T＆n种;吨++）
S = S +总和[T]
的printf（\ n此号为1的给定矩阵为％d \ N，S）;
}
INT getMatrix（）
{
FILE *输入= FOPEN（matrix.txt，R）;
焦炭℃;
INT女儿红= 0，I，J;
而（（C = GETC（输入））！='\ N'）
如果（c取代; ='0'和;＆安培;℃下='9'）
女儿红++;
地图=的malloc（女儿红* sizeof运算（INT *））;
倒带（输入）;
对于（i = 0; I＆LT;女儿红;我++）
{
图[我] =的malloc（女儿红*的sizeof（INT））;
为（J = 0; J＆LT;女儿红; J ++）
{
做
{
C = GETC（输入）;
}而（（c取代;！='0'和;＆安培;℃下='9'））;
地图[I] [J] = C-'0;
}
}
fclose函数（输入）;
返回女儿红;
}
这是更容易找到问题的时候，你首先描述你想要做什么。 总之，在我看来，你有问题的，如果你设置
我==（N-1），在初始化阶段，你进入这个如果statmnet是正确的，你不要每次都;吨减少I，
如果（我==（N-1））
{
总和[我] =计数;
计数= 0;
**一世 - ;**
}
其他
{
总和[I] =总和[1 + 1] +计数;
计数= 0;
一世 - ;
}
Assume a 2D [n][n] matrix containint only 1's and 0's. All the 1's in any row should come before 0's. The number of 1's in any row i should be at least the no, of 1's row (i+1). Find a method and write a c program to count the no of 1's in a 2D matrix. The complexity of the algorithm should be O(n).
The question is from Cormen's Algorithm Book, and below is my implementation for this problem. Kindly point out the mistakes in my algorithm and/or perhaps suggest a better way. Thanks!
#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;
}
it is easier to find problem when you first describe what you want to do. Anyway, seems to me that you have a problem on the if, you set
i == (n-1), on the initialization phase, and each time you enter this if the statmnet is correct and you don;t reduce i,
if (i==(n-1))
{
sum[i]=count;
count=0;
**i--;**
}
else
{
sum[i]=sum[i+1]+count;
count=0;
i--;
}
这篇关于制定一个O（N）算法发现没有1的从二维矩阵[N] [N]含1和0的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
