透過交換給定字串中包含“1”的索引處的相鄰元素來對陣列進行排序

---

對陣列進行排序意味著按升序排列陣列的所有元素。透過交換相鄰元素對陣列進行排序意味著我們只能交換彼此相鄰的元素，但我們可以交換任意次數的相鄰元素。我們將得到一個二進位制字串，該字串僅包含兩種字元“0”和“1”。如果給定字串中的任何字元為“0”，則我們不能將陣列中該索引處的元素與其相鄰元素交換。

示例

輸入 1

給定陣列：{1, 4, 3, 2, 5, 7, 6}

給定字串：0111011

輸出：是

解釋 − 在給定的陣列中，1 位於其位置，我們可以交換索引 1 到索引 3 的元素。我們可以將索引 1 的元素與下一個索引交換，然後將索引 2 與索引 3 交換，然後再次將索引 1 與索引 2 交換，使 2、3、4 處於排序形式。對於最後兩個元素，我們可以交換它們並獲得所需的排序陣列。

輸入 2

給定陣列：{1, 2, 4, 3, 5, 6}

給定字串：001011

輸出：否

解釋 − 在給定的陣列中，只有 3 和 4 不在其排序位置，並且索引 3 不能交換，這意味著無法透過交換來對陣列進行排序。

樸素方法

在這種方法中，我們將遍歷陣列並找到可排序的部分並對其進行排序。排序後，將檢查整個陣列是否已排序。如果排序，我們將列印是，否則列印否。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if the given array is sorted or not 
bool checkSorted(int arr[], int n){
   // traversing over the array 
   for(int i=1; i<n; i++){
      if(arr[i] < arr[i-1]){
         // means the current element is smaller as compared to the previous 
         return false;
      }
   }
   return true;
}
// function to sort the array 
bool isSorted(int arr[], int n, string str){
   // traversing over the given array 
   for(int i=0; i<n; i++){
      if(str[i] == '0'){
         // current index is not allowed to swap
         continue;
      }
      else if(arr[i] == i+1){
         // if the current index element is at the required position 
         // move to the next element 
         continue;
      }
      else{
         int j = i+1; // variable to traverse over the string
         while(j < n && str[j] == '1'){
            j++;
         }
         // sorting the sortable elements
         sort(arr+i,arr+j);
         i = j-1; // updating the value of i
      }
   }
   return  checkSorted(arr,n);
}
int main(){
   int arr[] = {1, 4, 3, 2, 5, 7, 6}; // given array 
   int n = 7; // size of array 
   string s = "0111011";    
   // calling the function 
   if(isSorted(arr,n,s)){
      cout<<"Yes, it is possible to sort the given array by swapping the allowed indexes";
   }
   else{
      cout<<"No, it is not possible to sort the given array by swapping the allowed indexes";
   }
   return 0;
}

輸出

Yes, it is possible to sort the given array by swapping the allowed indexes

時間和空間複雜度

上述程式碼的時間複雜度為 O(N*log(N))，其中 N 是陣列的大小。這裡的對數因子是由於使用 sort 函式對部分進行排序。

上述程式碼的空間複雜度為 O(1)，因為我們在這裡沒有使用任何額外的空間。

有效方法

在這種方法中，我們只會檢查可排序範圍內存在的所有元素是否僅屬於當前範圍，而不是執行實際排序。藉助這種方法，我們可以節省時間，時間複雜度將變為線性。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the solution  
bool isSorted(int arr[], int n, string str){
   // traversing over the given array 
   for(int i=0; i<n; i++){
      if(arr[i] == i+1){
         // if the current index element is at the required position 
         // move to the next element 
         continue;
      }
      else if(str[i] == '0'){
         // the current index element is not at the required position 
         // its not moveable also so return false 
         return false;
      }
      else{
         int j = i+1; // variable to traverse over the string
         while(j < n && str[j] == '1'){
            j++;
         }
         // we have limit now check if all the elements in the sortable 
         // limit is in the required final range             
         for(int k = i; k<j; k++){
            if(arr[k] <= i || arr[k] > j){
               return false;
            }
         }
         i = j-1; // updating the value of i
      }
   }
   return  true;
}
int main(){
   int arr[] = {1, 4, 3, 2, 5, 7, 6}; // given array 
   int n = 7; // size of array 
   string s = "0111011";    
   // calling the function 
   if(isSorted(arr,n,s)){
      cout<<"Yes, it is possible to sort the given array by swapping the allowed indexes";
   }
   else{
      cout<<"No, it is not possible to sort the given array by swapping the allowed indexes";
   }
   return 0;
}

輸出

Yes, it is possible to sort the given array by swapping the allowed indexes

時間和空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是陣列的大小。

上述程式碼的空間複雜度為 O(1)，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們實現了一個程式來檢查給定的當前陣列是否可以排序，如果排序是透過僅交換相鄰元素來完成的。此外，還給出了一個二進位制字串，指示哪些索引元素可以排序，哪些元素無法排序。我們實現了兩種方法，一種具有 O(N*log(N)) 的時間複雜度，另一種具有線性時間複雜度。