使用 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
以上是 使用 C++ 查找零的数量 的全部内容， 来源链接： utcz.com/z/297100.html
