設計一個算法來計算陣列中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 
    } 
}