数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用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
二分搜索 − 在二分搜索中，我们将通过根据中间元素是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
更新于：2022年2月11日
827 次查看
广告