Tìm Chỉ số của 0 được thay thế bằng 1 để có chuỗi 1 liên tục dài nhất trong mảng nhị phân - Bộ-2 trong C ++

Khái niệm

Đối với một mảng 0 và 1 đã cho, hãy xác định vị trí của 0 được thay thế bằng 1 để có được dãy 1s liên tục tối đa. Trong trường hợp này, độ phức tạp thời gian mong đợi là O (n) và không gian phụ trợ là O (1).

Đầu vào

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

Đầu ra

Index 10

Để chỉ số mảng bắt đầu từ 0, thay thế 0 bằng 1 tại

chỉ số 10 gây ra chuỗi 1s liên tục dài nhất.

Đầu vào

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

Đầu ra

Index 5

Phương pháp

Sử dụng số lượng các đơn vị trên cả hai mặt của 0 -

Bây giờ, khái niệm là đếm số lượng đơn vị ở cả hai phía của mỗi số 0. Ở đây, chỉ mục cần thiết được coi là chỉ số 0 có số lượng tối đa xung quanh nó. Các biến sau được thực hiện liên quan đến mục đích này -

• leftCnt - Nó được sử dụng để lưu trữ số lượng các đơn vị ở bên trái của phần tử hiện tại đang xem xét bằng 0.
• rightCnt - Nó được sử dụng để lưu trữ số lượng các đơn vị ở bên phải của phần tử hiện tại đang được xem xét bằng 0.
• maxIndex - Nó được coi là chỉ số bằng 0 với số lượng chỉ số tối đa xung quanh nó.
• lastInd - Nó được coi là chỉ mục của phần tử 0 cuối cùng được nhìn thấy
• maxCnt - Nó được coi là số lượng các đơn vị nếu số không ở chỉ mục maxI và được thay thế bằng một số.

Bây giờ chi tiết thủ tục được cung cấp bên dưới -

• Duy trì tăng dần rightCnt cho đến khi có một trong mảng đầu vào. Giả sử số 0 tiếp theo hiện diện tại chỉ mục i.

• Xác minh xem phần tử 0 này có phải là phần tử 0 đầu tiên hay không. Bây giờ, nó được coi là zeroelement đầu tiên nếu lastInd không giữ bất kỳ giá trị chỉ mục hợp lệ nào.

• Vì vậy, trong trường hợp đó, cập nhật lastInd được thực hiện với i. Hiện tại, giá trị của rightCnt là số ô ở bên trái của số 0 này.

• Kết quả của leftCnt này bằng rightCnt và sau đó xác định lại giá trị của rightCnt. Người ta thấy rằng nếu phần tử số 0 hiện tại không phải là số 0 đầu tiên, thì số phần tử xung quanh số 0 có mặt ở chỉ mục cuối cùng và được cung cấp bởi leftCnt + rightCnt.

• Bây giờ maxCnt sẽ chấp nhận giá trị leftCnt + rightCnt + 1 và maxIndex =lastInd nếu giá trị này nhỏ hơn giá trị hiện do maxCnt nắm giữ.

• Hiện tại rightCnt sẽ trở thành leftCnt bằng 0 tại chỉ mục i và lastInd sẽ bằng i. Bây giờ, hãy xác định giá trị của rightCnt, so sánh số lượng giá trị với maxCnt và cập nhật maxCnt và maxIndex cho phù hợp.

• Chúng ta phải lặp lại quy trình này cho từng phần tử 0 tiếp theo của mảng.

• Người ta đã quan sát thấy lastInd lưu trữ chỉ số bằng 0 mà leftCnt vàrightCnt hiện tại được tính toán.

• Cuối cùng, chỉ mục bắt buộc bằng 0 được thay thế bằng chỉ mục được lưu trữ trong maxIndex.

Ví dụ

// 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;
}

Đầu ra

Index of 0 to be replaced is 10