JavaScript 用于检查在旋转数组后是否可以对其进行排序

旋转数组意味着将每个索引的元素（除了一个端点）移动到右旋的下一个索引处，左旋则是移动到前一个索引处。右旋时，第0个索引取最后一个索引的值，左旋则相反。对数组进行排序意味着所有元素按正确的增序排列。我们将实现正确的代码，并提供解释以及时间和空间复杂度的讨论。

示例

Input: 5 6 9 10 2 3 3 4
Output: Yes

说明：我们可以将给定的数组旋转4次，得到排序后的数组。

First Rotation: 4 5 6 9 10 2 3 3
Second Rotation: 3 4 5 6 9 10 2 3
Third Rotation: 3 3 4 5 6 9 10 2
Fourth Rotation: 2 3 3 4 5 6 9 10

原生的方法

在这种方法中，主要思想是当旋转次数等于数组长度时，我们将得到相同的数组。因此，我们将数组旋转与其长度相等的次数，并且在每次旋转中，我们将使用双指针和交换方法。在每次旋转时，我们将检查当前数组是否已排序。

示例

// function to rotate the given array
function rotate(arr){
   var l = 0;
   var r = arr.length-1;
   while(l < r){
      arr[l] += arr[r];
      arr[r] = arr[l]-arr[r];
      arr[l] = arr[l]-arr[r];
      l++;
   }
   return arr;
}

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length

   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
   var k = arr.length
   while(k--){
      if(increasing(arr)){
         console.log("The given array can be sorted after " + (arr.length-k-1) + " rotations");
         return
      }
      arr = rotate(arr);
   }
   console.log("The given array cannot be sorted");
}

//defining the given array
var arr = [5, 6, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);

// calling the function
check(arr);

输出

Given array is: 5,6,9,10,2,3,3,4
The given array can be sorted after 4 rotations

时间和空间复杂度

以上代码的时间复杂度为O(N*N），其中N是数组的大小。我们将数组旋转N次，每次旋转需要N个移动。

以上代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。

高效的方法

先前代码的时间复杂度很高，可以通过观察来降低。如果给定的数组是排序的，或者排序为两部分，第二部分的元素小于或等于第一半元素，并且两半自身排序。

示例

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of the array
   var len = arr.length

   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return arr[len-1] <= arr[0];
}

// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
   if(increasing(arr)){
      console.log("The given array can be sorted after ");
   }
   else{
      console.log("The given array cannot be sorted");
   }
}

//defining the given array
var arr = [5, 4, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);

// calling the function
check(arr);

输出

Given array is: 5,4,9,10,2,3,3,4
The given array cannot be sorted

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是数组的大小。我们只对数组进行了一次遍历。

上述代码的空间复杂度为O(1)，因为我们没有使用额外的空间。

结论

在本教程中，我们实现了一个JavaScript代码来检查是否可以通过旋转元素来对数组进行排序。旋转数组意味着将每个索引的元素（除了一个端点）移动到右旋转的下一个索引或左旋转的前一个索引。我们实现了两种方法，一种时间复杂度为O(N*N)，另一种为O(N)。