แนวคิด
เมื่อได้รับอาร์เรย์ของ 0 และ 1 ให้หาตำแหน่งของ 0 ที่ควรแทนที่ด้วย 1 เพื่อให้ได้ maximum continuous sequence of 1s ในกรณีนี้ expected time complexity คือ O(n) และ auxiliary space คือ O(1)
อินพุต
arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}เอาต์พุตIndex 10
ให้ array index เริ่มจาก 0 การแทนที่ 0 ด้วย 1 ที่
index 10 ทำให้ได้ longest continuous sequence of 1s
อินพุต
arr[] = {1, 1, 1, 1, 1, 0}เอาต์พุต
Index 5
วิธีการ
ใช้จำนวน ones ทั้งสองข้างของศูนย์ −
แนวคิดคือนับจำนวน ones ทั้งสองข้างของแต่ละศูนย์ index ที่ต้องการถือเป็น index ของศูนย์ที่มีจำนวน ones รอบๆ มากที่สุด ตัวแปรต่อไปนี้ถูกใช้เพื่อวัตถุประสงค์นี้ −
- leftCnt − ใช้เก็บจำนวน ones ด้านซ้ายของ current element zero ที่พิจารณา
- rightCnt − ใช้เก็บจำนวน ones ด้านขวาของ current element zero ที่พิจารณา
- maxIndex − ถือเป็น index ของศูนย์ที่มีจำนวน ones รอบๆ มากที่สุด
- lastInd − ถือเป็น index ของ last zero element ที่เห็น
- maxCnt − ถือเป็นจำนวน ones หากศูนย์ที่ index maxInd ถูกแทนที่ด้วย one
รายละเอียดขั้นตอนการทำงานด้านล่าง −
รักษาการเพิ่ม rightCnt จนกว่าจะมี one ใน input array สมมติว่าศูนย์ถัดไปอยู่ที่ index i
ตรวจสอบว่าศูนย์ element นี้เป็น first zero element หรือไม่ ตอนนี้มันถือเป็น first zero element ถ้า lastInd ไม่มีค่า index ที่ถูกต้อง
ในกรณีนั้น การอัปเดต lastInd ทำกับ i ตอนนี้ค่าของ rightCnt คือจำนวนศูนย์ด้านซ้ายของศูนย์นี้
ผลลัพธ์คือ leftCnt เท่ากับ rightCnt และจากนั้นหาค่าของ rightCnt อีกครั้ง พบว่าถ้า current zero element ไม่ใช่ first zero จำนวน ones รอบๆ ศูนย์ที่อยู่ที่ index lastInd จะได้จาก leftCnt + rightCnt
ตอนนี้ maxCnt จะรับค่า leftCnt + rightCnt + 1 และ maxIndex = lastInd ถ้าค่านี้มากกว่าค่าที่ maxCnt ถืออยู่ในปัจจุบัน
ตอนนี้ rightCnt จะกลายเป็น leftCnt สำหรับศูนย์ที่ index i และ lastInd จะเท่ากับ i ตอนนี้หาค่าของ rightCnt อีกครั้ง เปรียบเทียบจำนวน ones กับ maxCnt และอัปเดต maxCnt และ maxIndex ตามลำดับ
เราต้องทำซ้ำขั้นตอนนี้สำหรับ zero element ต่อไปของอาร์เรย์
สังเกตได้ว่า lastInd เก็บ index ของศูนย์ที่ current leftCnt และ rightCnt ถูกคำนวณ
สุดท้าย index ที่ต้องการของศูนย์ที่จะถูกแทนที่ด้วยหนึ่งถูกเก็บใน maxIndex
ตัวอย่างโค้ด
// โปรแกรม C++ เพื่อหา index ของศูนย์ // ที่จะถูกแทนที่ด้วยหนึ่งเพื่อให้ได้ // longest continuous sequence of ones #include <bits/stdc++.h> using namespace std; // ใช้คืนค่า index ของ 0 ที่จะถูกแทนที่ // ด้วย 1 เพื่อให้ได้ longest continuous // sequence of 1s ถ้าไม่มี 0 // ในอาร์เรย์ จะคืนค่า -1 int maxOnesIndex(bool arr1[], int n1){ int i = 0; // ใช้เก็บจำนวน ones ด้านซ้าย // ของ current element zero int leftCnt1 = 0; // ใช้เก็บจำนวน ones ด้านขวา // ของ current element zero int rightCnt1 = 0; // แสดง index ของศูนย์ที่มีจำนวน // ones รอบๆ มากที่สุด int maxIndex1 = -1; // แสดง index ของ last zero element ที่เห็น int lastInd1 = -1; // แสดงจำนวน ones หากศูนย์ที่ index // maxInd1 ถูกแทนที่ด้วยหนึ่ง int maxCnt1 = 0; while (i < n1) { // ใช้เพิ่ม count จนกว่า // current element จะเป็น 1 if (arr1[i]) { rightCnt1++; } else { // สังเกตได้ว่าถ้า current zero element // ไม่ใช่ first zero element // แล้วนับจำนวน ones // ที่ได้จากการแทนที่ศูนย์ที่ // index lastInd อัปเดต maxCnt // และ maxIndex ถ้าจำเป็น if (lastInd1 != -1) { if (rightCnt1 + leftCnt1 + 1 > maxCnt1) { maxCnt1 = leftCnt1 + rightCnt1 + 1; maxIndex1 = lastInd1; } } lastInd1 = i; leftCnt1 = rightCnt1; rightCnt1 = 0; } i++; } // หาจำนวน ones ใน continuous // sequence เมื่อ last zero element ถูก // แทนที่ด้วยหนึ่ง if (lastInd1 != -1) { if (leftCnt1 + rightCnt1 + 1 > maxCnt1) { maxCnt1 = leftCnt1 + rightCnt1 + 1; maxIndex1 = lastInd1; } } return maxIndex1; } // Driver function int main(){ bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 }; // bool arr1[] = {1, 1, 1, 1, 1, 0}; int n1 = sizeof(arr1) / sizeof(arr1[0]); cout << "Index of 0 to be replaced is " << maxOnesIndex(arr1, n1); return 0; }เอาต์พุต
Index of 0 to be replaced is 10
