資料結構
網路
關係資料庫管理系統(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 次檢視
廣告