C++を使用してゼロの数を見つけます

この問題では、0と1のみで構成されるバイナリ配列bin[]が与えられます。私たちのタスクは、ゼロの数を見つけることです。 。

配列は並べ替えられます。つまり、すべての0は1の後に一緒に配置されます。

問題を理解するために例を見てみましょう

入力

arr[] = {1, 1, 1, 0, 0, 0, 0}

出力

4

ソリューションアプローチ

この問題の簡単な解決策は、配列が並べ替えられているという事実を使用することです。つまり、配列内の0の数は、配列内で最初に出現する0を使用して見つけることができます。最初の発生後と同様に、すべての値はゼロになります。

配列内で最初に出現する0を見つけるため。検索アルゴリズムを使用できます。

線形探索-最初の0の線形探索では、最初の0が検出されなくなるまで配列全体をトラバースし、配列の最初の出現とサイズを使用してカウントを返します。このソリューションを使用して、問題の時間計算量をO（N）にします。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findFirstZero(int arr[], int n){
   for(int i = 0; i < n; i++){
      if(arr[i] == 0){
         return i;
      }
   }
   return -1;
}
int countZerosArr(int arr[], int n){
   int firstOccZero = findFirstZero(arr, n);
   if (firstOccZero == -1)
      return 0;
      return (n - firstOccZero);
   }
int main(){
   int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
   return 0;
}

出力

The count of zeros in array is 5

二分探索-二分探索では、midの要素が1であるか0であるかに基づいて配列のセクションを分割することにより、最初の0を見つけます。そして0の最初の出現のインデックスを返します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findFirstZero(int arr[], int start, int end){
   if (end >= start){
      int mid = start + (end - start) / 2;
      if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
         return mid;
      if (arr[mid] == 1)
         return findFirstZero(arr, (mid + 1), end);
      else
         return findFirstZero(arr, start, (mid -1));
   }
   return -1;
}
int countZerosArr(int arr[], int n){
   int firstOccZero = findFirstZero(arr, 0, n - 1);
   if (firstOccZero == -1)
      return 0;
      return (n - firstOccZero);
}
int main(){
   int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
   return 0;
}

出力

The count of zeros in array is 7