设计一个算法来计算阵列中1的个数A nxn

Question

假设一个nxn数组A的每一行由1和0组成，这样在A的任意一行中，所有的1都会出现在任何0之前进一步假设第i行中的1的数目至少是第i + 1行中的数目，对于i = 0,1,2，...，n-2 假设A已经在内存中，描述方法运行O（n）时间来计算阵列A中1的数量。

所以我的方法是从A [n-1,0]开始，如果== 1，我们添加1的数字，否则我们去up and right so so scan A moving only right to the right and up

Answer 1

双回路：

SUM = 0 
j = 0 
for i from n-1 to 0 step -1 do { 
    while (j<n)and(A[i,j]==1) do { 
    j = j+1 
    } 
    SUM = SUM+j 
} 

一环：

SUM = 0 
i = n-1 
j = 0 
while (i>=0)and(j<n) do { 
    if A[i,j]==1 then { 
    j = j+1 
    } else { 
    SUM = SUM+j 
    i = i-1 
    } 
}