ค้นหาดัชนี 0 ที่จะแทนที่ด้วย 1 เพื่อรับลำดับต่อเนื่องที่ยาวที่สุดของ 1 วินาทีในอาร์เรย์ไบนารี - Set-2 ใน C ++

แนวคิด

สำหรับอาร์เรย์ที่กำหนดของ 0 และ 1 ให้กำหนดตำแหน่งของ 0 ที่จะแทนที่ด้วย 1 เพื่อให้ได้ลำดับต่อเนื่องสูงสุด 1 วินาที ในกรณีนี้ ความซับซ้อนของเวลาที่คาดหวังคือ O(n) และช่องว่างเสริมคือ O(1)

อินพุต

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

ผลลัพธ์

Index 10

ให้ดัชนีอาร์เรย์เริ่มต้นจาก 0 แทนที่ 0 ด้วย 1 ที่

ดัชนี 10 ทำให้เกิดลำดับต่อเนื่องที่ยาวที่สุดของ 1 วินาที

อินพุต

arr[] = {1, 1, 1, 1, 1, 0}

ผลลัพธ์

Index 5

วิธีการ

ใช้การนับหนึ่งบนทั้งสองข้างของศูนย์ −

ตอนนี้ แนวคิดคือการนับจำนวนตัวทั้งสองข้างของศูนย์แต่ละตัว ในที่นี้ ดัชนีที่กำหนดจะถือเป็นดัชนีของศูนย์ที่มีจำนวนสูงสุดของดัชนีอยู่รอบๆ ตัวแปรต่อไปนี้ถูกนำมาใช้เกี่ยวกับจุดประสงค์นี้ -

• leftCnt − มันถูกใช้เพื่อเก็บจำนวนคนที่อยู่ทางด้านซ้ายขององค์ประกอบปัจจุบันที่มองข้ามเป็นศูนย์
• rightCnt − มันถูกใช้เพื่อเก็บการนับจำนวนทางด้านขวาขององค์ประกอบปัจจุบันที่มองข้ามเป็นศูนย์
• maxIndex − จะถือว่าเป็นดัชนีของศูนย์โดยมีจำนวนสูงสุดของดัชนีอยู่รอบๆ
• lastInd - ถือว่าเป็นดัชนีขององค์ประกอบศูนย์สุดท้ายที่เห็น
• maxCnt - จะถือว่าเป็นการนับหนึ่งถ้าศูนย์ที่ดัชนี maxInd ถูกแทนที่ด้วยหนึ่ง

ตอนนี้รายละเอียดขั้นตอนได้รับด้านล่าง -

• รักษาการเพิ่ม rightCnt จนกว่าจะมีหนึ่งในอาร์เรย์อินพุต สมมติว่ามีศูนย์ถัดไปอยู่ที่ดัชนี i

• ตรวจสอบว่าองค์ประกอบศูนย์นี้เป็นองค์ประกอบศูนย์แรกหรือไม่ ตอนนี้จะถือว่าเป็นองค์ประกอบศูนย์แรกหาก lastInd ไม่มีค่าดัชนีที่ถูกต้อง

• ดังนั้นในกรณีนั้นการอัปเดต lastInd เสร็จสิ้นด้วย i ในปัจจุบันค่าของ rightCnt คือจำนวนศูนย์ทางด้านซ้ายของศูนย์นี้

• จากผลลัพธ์ของ leftCnt นี้เท่ากับ rightCnt จากนั้นกำหนดค่าของ rightCnt อีกครั้ง จะเห็นได้ว่าหากองค์ประกอบศูนย์ปัจจุบันไม่ใช่ศูนย์แรก จำนวนขององค์ประกอบรอบศูนย์จะมีอยู่ที่ดัชนี lastInd โดย leftCnt + rightCnt

• ตอนนี้ maxCnt จะยอมรับค่า leftCnt + rightCnt + 1 และ maxIndex =lastInd หากค่านี้น้อยกว่าค่าที่ maxCnt ถืออยู่ในปัจจุบัน

• ในปัจจุบัน rightCnt จะกลายเป็น leftCnt สำหรับศูนย์ที่ดัชนี i และ lastInd จะเท่ากับ i ตอนนี้กำหนดค่าของ rightCnt อีกครั้ง เปรียบเทียบจำนวนกับ maxCnt และอัปเดต maxCnt และ maxIndex ตามลำดับ

• เราต้องทำซ้ำขั้นตอนนี้สำหรับแต่ละองค์ประกอบศูนย์ที่ตามมาของอาร์เรย์

• สังเกตได้ว่า LastInd เก็บดัชนีศูนย์ซึ่งคำนวณ leftCnt และ rightCnt ปัจจุบัน

• สุดท้าย ดัชนีที่จำเป็นของศูนย์ที่จะแทนที่ด้วยดัชนีหนึ่งจะถูกเก็บไว้ใน maxIndex

ตัวอย่าง

// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;
// Used to returns index of 0 to be replaced
// with 1 to get longest continuous
// sequence of 1s. If there is no 0
// in array, then it returns -1.
int maxOnesIndex(bool arr1[], int n1){
   int i = 0;
   // Used to store count of ones on left
   // side of current element zero
   int leftCnt1 = 0;
   // Used to store count of ones on right
   // side of current element zero
   int rightCnt1 = 0;
   // Shows index of zero with maximum number
   // of ones around it.
   int maxIndex1 = -1;
   // Shows index of last zero element seen
   int lastInd1 = -1;
   // Shows count of ones if zero at index
   // maxInd1 is replaced by one.
   int maxCnt1 = 0;
   while (i < n1) {
      // Used to keep incrementing count until
      // current element is 1.
      if (arr1[i]) {
         rightCnt1++;
      }
      else {
         // It has been observed that if current zero element
         // is not first zero element,
         // then count number of ones
         // obtained by replacing zero at
         // index lastInd. Update maxCnt
         // and maxIndex if required.
         if (lastInd1 != -1) {
            if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
               maxCnt1 = leftCnt1 + rightCnt1 + 1;
               maxIndex1 = lastInd1;
            }
         }
         lastInd1 = i;
         leftCnt1 = rightCnt1;
         rightCnt1 = 0;
      }
      i++;
   }
   // Determine number of ones in continuous
   // sequence when last zero element is
   // replaced by one.
   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