資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢必須設定位以最大化下一個設定位之間距離的索引
給定一個數組，其中只包含二進位制數字“0”和“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，因為如果慢指標為 -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) 或常數。
注意：給定的初始陣列中將至少存在一個設定位，否則獲取任意兩個設定位之間的距離將沒有任何意義。
結論
在本教程中，我們實現了一個程式來查詢我們建立的一個設定位之間兩個設定位之間的最大距離。我們使用了雙指標方法透過 while 迴圈遍歷陣列並將答案儲存在一個變數中。上述程式碼的時間複雜度為 O(N)，因為我們只遍歷了陣列一次，並且沒有消耗額外的空間。
81 次檢視
