Trong bài toán này, chúng ta được cung cấp một bin mảng nhị phân [] chỉ bao gồm 0 và 1. Nhiệm vụ của chúng ta là tìm số 0 .
Mảng được sắp xếp tức là tất cả các số 0 được sắp xếp cùng nhau sau 1 ô.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 1, 1, 0, 0, 0, 0} Đầu ra
4
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng thực tế là mảng được sắp xếp, đó là số lượng 0 trong mảng có thể được tìm thấy bằng cách sử dụng lần xuất hiện đầu tiên của 0 trong mảng. Vì sau lần xuất hiện đầu tiên, tất cả các giá trị sẽ bằng không.
Để tìm lần xuất hiện đầu tiên của 0 trong mảng. Chúng tôi có thể sử dụng các thuật toán tìm kiếm.
Tìm kiếm tuyến tính - Trong tìm kiếm tuyến tính cho số 0 đầu tiên, chúng tôi sẽ duyệt qua toàn bộ mảng cho đến khi không gặp số 0 đầu tiên, sau đó chúng tôi sẽ trả về số lượng sử dụng lần xuất hiện đầu tiên và kích thước của mảng. Sử dụng giải pháp này, chúng tôi làm cho độ phức tạp về thời gian của vấn đề là O (N).
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The count of zeros in array is 5
Tìm kiếm nhị phân - trong tìm kiếm nhị phân, chúng ta sẽ tìm số 0 đầu tiên bằng cách chia phần của mảng dựa trên phần tử ở giữa là 1 hay 0. Và trả về chỉ số của lần xuất hiện đầu tiên là 0.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The count of zeros in array is 7