假設一個[n][n]1 和 0 的二維矩陣。任何一行中的所有 1 都應該在 0 之前。任何行i中 1 的數量至少應為 1 的行數i 1。找到一個方法，撰寫一個復雜度為 O(n) 的 Java 程式來計算陣列中的 1。
例如，我們有以下陣列：
{{1,1,1,1},
{1,1,1,1},
{1,1,0,0},
{1,0,0,0}}
我撰寫了一個正確計算 1 的代碼，但我不確定復雜度是 O(n) 還是 O(n^2)。
代碼如下：
public class SpecialMatrix {
public static void main(String[] args) {
int[][] a = {{1,1,1,1},
{1,1,1,1},
{1,1,0,0},
{1,0,0,0}};
int n = 4;
int cnt=0;
int row;
int col = 0;
for (row = n-1; row>=0; row--)
{
while(col<n && a[row][col]==1)
{
cnt = cnt (row 1);
System.out.print("Row: " row " Col: " col " Cnt: " cnt);
System.out.println();
col ;
}
System.out.println();
}
System.out.print(cnt);
}
}
輸出如下所示：
Row: 3 Col: 0 Cnt: 4
Row: 2 Col: 1 Cnt: 7
Row: 1 Col: 2 Cnt: 9
Row: 1 Col: 3 Cnt: 11
11
我想要一些關于代碼復雜性的幫助。是 O(n) 還是 O(n^2)？
謝謝！
uj5u.com熱心網友回復：
您的外部回圈必須始終執行n時間。你不能改變它。col 因此，當您利用行之間的關系計算計數時，內部while回圈row/col由 1根據col to row比較的結果，內部回圈可能會在任何地方執行0 to n多次，僅此而已。所以它運行在O(n)
進入內回圈的次數以及外回圈的迭代次數取決于 1 和 0 的特定分組
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520468.html
標籤：爪哇数组算法
上一篇：如何從串列中獲取整數？
下一篇：計算排列中的排列數