使用 C++ 查找零的数量

在这个问题中，我们得到一个二进制数组 bin[]，只包含 0 和 1。我们的任务是找出零的数量。

数组已排序，即所有 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<<"数组中零的计数是 "<<countZerosArr(arr, n);
   return 0;
}

输出结果

数组中零的计数是 5

Binary Search - 在二分搜索中，我们将通过根据中间元素是 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<<"数组中零的计数是 "<<countZerosArr(arr, n);
   return 0;
}

输出结果

数组中零的计数是 7