ในปัญหานี้ เราได้รับอาร์เรย์ไบนารี bin[] ที่ประกอบด้วยแค่ 0 และ 1 ภารกิจของเราคือ หาจำนวนศูนย์
อาร์เรย์ถูกจัดเรียงแล้ว คือ 0 ทั้งหมดถูกจัดกลุ่มไว้ด้วยกันหลัง 1
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {1, 1, 1, 0, 0, 0, 0}
เอาต์พุต
4
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการใช้ข้อเท็จจริงว่าอาร์เรย์จัดเรียงแล้ว คือ จำนวน 0 ในอาร์เรย์สามารถหาได้โดยการใช้การเกิดขึ้นครั้งแรกของ 0 ในอาร์เรย์ เนื่องจากหลังการเกิดครั้งแรก ค่าทั้งหมดจะเป็นศูนย์
สำหรับการหาการเกิดครั้งแรกของ 0 ในอาร์เรย์ เราสามารถใช้อัลกอริทึมค้นหา
Linear Search - ในการค้นหาแบบเชิงเส้นสำหรับ 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 - ใน binary search เราจะหา 0 แรกโดยการแบ่งส่วนของอาร์เรย์ตามว่าองค์ประกอบที่ mid เป็น 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
