Trong bài toán này, chúng ta được cung cấp một bin mảng [] bao gồm các giá trị boolean (chỉ có 0 và 1) theo thứ tự được sắp xếp. Nhiệm vụ của chúng tôi là tìm chỉ mục của 1 đầu tiên trong một mảng được sắp xếp của 0 và 1 .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : bin[] = {0, 0, 0, 1, 1}
Output : 3 Giải thích -
First 1 of the binary array is encountered at index 3.
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, về cơ bản chúng ta cần tìm chỉ số của 1 1 trong mảng. Để làm được điều đó, chúng tôi có thể sử dụng kỹ thuật tìm kiếm.
Một cách tiếp cận có thể là sử dụng tìm kiếm tuyến tính, chúng tôi sẽ duyệt qua mảng từ chỉ số 0 đến cuối mảng. Và trả về chỉ số của 1 đầu tiên trong mảng, nếu không thì in ra -1.
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;
double find1stOneInArray(int bin[], int n) {
for (int i = 0; i < n; i++)
if (bin[i] == 1)
return i;
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
} Đầu ra
The index of 1st occurrence of 1 in array is 3
Một kỹ thuật tìm kiếm khác có thể được sử dụng là tìm kiếm nhị phân vì mảng được sắp xếp.
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;
double find1stOneInArray(int bin[], int n) {
int low = 0;
int high = (n - 1);
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
return mid;
else if (bin[mid] == 1)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
} Đầu ra
The index of 1st occurrence of 1 in array is 3