通过交换给定字符串中包含“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)) 的时间复杂度，另一种具有线性时间复杂度。