C++ 找到必须设置为1的位的索引，以最大化下一个设置位之间的距离

给定一个仅包含二进制数字’0’和’1’的数组。我们必须将给定数组中之前不是设置位的位设置为1，使得最终数组中设置位之间的索引数达到可能的最大距离。

示例

输入

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

输出

3

解释： 如果我们将索引为3的位翻转，它将与0和6索引的距离均为3。对于其他所有索引，距离都小于3。

输入：

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

输出

3

说明 ：我们可以翻转零索引的位，得到距离为3，对于其他可能的索引，如索引1为2，索引2、4和5为1。

方法

我们已经看过上面的问题解释和例子，现在让我们来看看实现代码所需的步骤：

• 首先，我们将创建一个函数，其中我们将传递数组和数组的长度作为参数，并返回一个整数。

• 我们将创建两个指针，一个是慢指针，最初为-1，始终指向我们找到的最后一个设置位。

• 快指针将遍历数组，并每次增加一个。

• 在每个设置位处，我们将检查慢指针是否为-1，因为如果慢指针为-1，则表示我们可以设置第0个索引的位，否则我们需要设置中间索引的位。

• 在每个设置位处，我们将检查中间位置，并在需要时更新答案，还将将慢指针的位置更新为当前索引。

• 在循环结束时，我们将检查最后一个索引处的设置位可能性，并在可能时更新答案的值。

例子

#include <bits/stdc++.h>
using namespace std;

// function to find the required maximum distance we will change only 1 bit from it 
int findDis(int arr[], int len){
    int slow = -1, fast = 0;
    int ans = 0; // variable to store the answer 
    // iterating over the array using the pointers and while loop
    while(fast < len ){
       // if the current index value is 1 
       if(arr[fast] == 1){
          // if the slow pointer is at -1 means we hit the first index that contains 1 and now we can flip the value at the zeroth index
          if(slow == -1 ){
             // if fast is set bit we cannot flip a zero here 
             if(fast == 0){
                slow = fast;
                fast++; // moving to the next index 
                continue;
             }
             ans = max(ans, fast - slow);
             slow = fast; 
          } else{
             // in this case we will always flip the middle index value 
             ans = max(ans, (fast-slow+1)/2);
             slow = fast; // increasing slow pointer to current pointer 
          }
       }
       fast++; // moving to the next index 
    }
    // now check if we can flip the last index 
    ans = max(ans, len -1 -slow); 
    return ans;// returning the final answer 
}

int main(){
   int arr[] = {1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1}; // given array 
    // getting the size of the array 
    int len = sizeof(arr)/ sizeof(arr[0]);
   cout << "The maximum distance at which we can mark the set bit is " << findDis(arr, len) << endl;
    return 0;
}

输出

The maximum distance at which we can mark the set bit is 3

时间和空间复杂度

上面代码的时间复杂度是O(N)，其中N是给定数组的大小。我们只是遍历一次数组，使得时间复杂度是线性的。

在这个程序中，我们没有使用任何额外的空间，这使得上面代码的时间复杂度是O(1)，即常数。

注意：给定的初始数组中至少会存在一个设置的位，否则获取任意两个设置位之间的距离将没有意义。

结论

在本教程中，我们实现了一个程序，用于找到两个设置位之间的最大距离，其中一个设置位是由我们创建的。我们使用了双指针的方法来遍历数组，并将答案存储在一个变量中。上面代码的时间复杂度是O(N)，因为我们只遍历了一次数组，而且没有使用额外的空间。