ให้อาร์เรย์ไบนารี (มีแค่ 0 และ 1) หาตำแหน่งของ 0 ที่ถ้าเปลี่ยนเป็น 1 จะได้ลำดับ 1 ต่อเนื่อง (Contiguous) ยาวที่สุด
ตัวอย่าง: arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] → คำตอบคือ Index 9
อัลกอริทึม
ติดตาม 3 ตัวแปร: current index (curr), previous zero (pz), previous-previous zero (ppz)
เมื่อเจอ 0: คำนวณ curr - ppz หากมากกว่าค่าสูงสุด อัปเดตค่าสูงสุดและบันทึก index ของ pz
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int findIndex(bool arr[], int n) {
int count_max = 0;
int index = -1;
int pz = -1; // previous zero
int ppz = -1; // previous-previous zero
for (int curr = 0; curr < n; curr++) {
if (arr[curr] == 0) {
if (curr - ppz > count_max) {
count_max = curr - ppz;
index = pz;
}
ppz = pz;
pz = curr;
}
}
// ตรวจสอบกรณีท้ายอาร์เรย์
if (n - ppz > count_max)
index = pz;
return index;
}
int main() {
bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Index of 0 to be replaced is " << findIndex(arr, n);
return 0;
}
ผลลัพธ์
Index of 0 to be replaced is 9
ความซับซ้อน
เวลา: O(n), พื้นที่: O(1)
