0と1を含むソートされた配列からのゼロの数を数えるためのアルゴリズム。

Question

入力配列の0の総数を数えるアルゴリズムの実行時間を改善しようとしています。入力配列は長さnを持ち、ソート順に並べられた0と1から構成されています。これまで

マイアルゴリズムされています。しかし、実行時間がO（n）は

public int zeroCount(int[] a){ 

    if(a[0]==1) 
    return 0; 
    int length =a.length; 
    if(a[length-1]==0) 
     return length; 
    int count=0; 
    for(int i=0;i<length&&a[i]==0;i++){ 
      count++; 
    } 

    return count; 
} 

：

Algorithm : zeroCount(A) 
Input : An sorted array A containing 0s and 1s 
Output : total number of 0s in A 

if A[0]=1 then 
    return 0; 
len <— A.length 
if A[len-1]=0 then 
    return len 
count <— 0 
i <—0 
for i<len do   
    if A[i]==0 then 
     count++ 
    i++ 
return count 

のJava実装がされています。このアルゴリズムの実行時間を改善するための提案があれば歓迎されます。

Answer 1

入力配列はすでにソートされているので、バイナリ検索を使用してパフォーマンスを向上させることができます。これにより、実行時間がO（log n）に改善されます。

バイナリ検索を使用するアルゴリズムは次のとおりです。

Algorithm : zeroCount(A) 
Input : sorted array A containing 0s and 1s 
Output : total number of 0s in A 

if A[0]=1 then 
    return 0; 
len <— A.length 
if A[len-1]=0 then 
    return len 
return count(A,0,length) 


Algorithm : count(A,lower,upper) 
Input : sorted array A , integers lower and upper 
Output : total number of 0s in A 

mid <— (lower+upper)/2 

if A[mid] != A[mid-1] then 
    return mid 

if A[mid] != A[mid+1] then 
    return mid+1 

if A[mid] = 1 then 
    return count(A,lower,mid-1) 

if A[mid] = 0 then 
     return count(A,mid+1,upper) 

Java実装：

public int zeroCount(int[] a) { 

    if (a[0] == 1) // all are 1 
     return 0; 
    int length = a.length; 
    if (a[length - 1] == 0) //all are 0 
     return length; 

    return count(a, 0, length); 
} 

public int count(int[] a, int lower, int upper) { 
    int mid = (lower + upper)/2; 
    if (a[mid] != a[mid - 1]) 
     return mid; 

    if (a[mid] != a[mid + 1])  
     return mid + 1; 

    if (a[mid] == 1) {    // all are 1 above mid 
     return count(a, lower, mid - 1); 
    } else if (a[mid] == 0) {    // all are 0 below mid 
     return count(a, mid + 1, upper); 
    } 
    return 0; 
} 

Answer 2

あなたの配列に0の最後に出現する（たとえば、インデックスのi）を見つけるためにバイナリ検索を微調整することができます。その後、0のカウントは（i + 1）になります。

int CountOfZeroes(int[] A, int key) 
     { 
      int low = 0; 
      int high = A.size - 1;    
      int result = -1; 

      while (low <= high) 
      { 
       int mid = low + (high-low)/2; 

       if (A[mid] == key) 
       { 
        result = mid; 
        low = mid + 1; 
       } 
       else if (key < A[mid]) 
       { 
        high = mid - 1; 
       } 
       else 
       { 
        low = mid + 1; 
       } 
      } 

      return result + 1;    
     } 

キーを0に設定して上記の機能を呼び出します。時間の複雑さはO(log n)になります。