ในปัญหานี้ เราได้รับ Binary Array 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<<"The count of zeros in array is "<<countZerosArr(arr, n);
return 0;
} ผลลัพธ์
The count of zeros in array is 5
Binary Search - ในการค้นหาแบบไบนารี เราจะพบ 0 ตัวแรกโดยแบ่งส่วนของอาร์เรย์โดยพิจารณาว่าองค์ประกอบที่อยู่ตรงกลางคือ 1 หรือ 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
