JavaScript 检查数组是否已排序且已旋转

已排序的数组是指所有元素按增序排列的数组。我们给出了一个大小为N的数组和一个包含不同整数的数组（也就是每个整数只出现一次）。我们需要检查数组是否以顺时针方向排序和旋转。如果数组已排序且已旋转，则返回”YES”；否则，返回”NO”。

注意 − 这里我们讨论的是已排序和旋转的意思至少要存在一次旋转。我们不能把已排序的数组当作已排序和旋转的数组。

假设我们给出了一个大小为N的数组：

输入

N = 5
Array = [5, 1, 2, 3, 4]

输出

Yes, the given array is sorted and rotated.

解释

一个数组是经过一个位置的排序的数组和旋转

Sorted array = [1, 2, 3, 4, 5]
Rotated above sorted array by 1 place, we get = [5, 1, 2, 3, 4]

排好序并旋转一个位置后，可以与输入数组匹配，所以输出为：是的。

输入

N = 6
Array = [6, 5, 1, 2, 3, 4]

输出

No, the given array is not sorted and rotated array.

解释

给定的数组是一个未排序且旋转过的数组

Sorted array = [1, 2, 3, 4, 5, 6]
Rotated above sorted array by 1 place, we get = [6, 1, 2, 3, 4, 5]
Rotated above sorted array by 2 place, we get = [5, 6, 1, 2, 3, 4]
Rotated above sorted array by 3 place, we get = [4, 5, 6, 1, 2, 3]
Rotated above sorted array by 4 place, we get = [3, 4, 5, 6, 1, 2]
Rotated above sorted array by 5 place, we get = [2, 3, 4, 5, 6, 1]

以上排序和旋转的数组都不与输入数组匹配，因此答案是“否”。

方法

这里我们将讨论两种方法。让我们在下面的部分看到它们−

方法1：通过查找枢轴元素（最小值）来检查数组是否已排序和旋转

这种方法的思想是我们将找到最小的数字，如果我们的数组已排序和旋转，最小数之前和之后的值应该是排序的。

示例

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var mi = Number.MAX_VALUE; // variable to find the smallest number 
   var idx_min = -1; // variable to store the index of smallest number;

   // traversing over the array to find the minimum element and its index
   for(var i = 0; i < len; i++){
      if (arr[i] < mi){
         mi = arr[i];
         idx_min = i;
      }
   }

   // traversing over the array to find that all the elements 
   // before the minimum element are sorted 
   for(var i = 1; i < idx_min; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }

   // traversing over the array to find that all the elements after the minimum element are sorted 
   for(var i = idx_min + 1; i < len; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }

   // checking if the last element of the array is smaller than the first element or not 
   if(arr[len-1] > arr[0]){
      return false;
   }
   else{
      return true;
   }
}

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

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

时间复杂度 – O(N)，其中N是数组的大小。

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

方法2：通过计算相邻逆序对数检查数组是否已排序且旋转

这种方法的思想是我们将遍历数组并检查前一个元素是否小于当前元素。对于已排序和旋转的数组，如果前一个元素大于当前元素，则逆序对数必须为1，否则数组不是已排序且旋转的。

示例

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var count = 0; // variable to count the adjacent inversions

   // traversing over the array to find the number of times first element is smaller than second 
   for(var i = 1; i < len; i++){
      if (arr[i] < arr[i-1]){
         count++;
      }
   }

   // checking if the last element of the array is smaller 
   // than the first element or not and inversion must be equal to 1
   if(arr[len-1] > arr[0] || count != 1){
      return false;
   }
   else{
      return true;
   }
}

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

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

时间复杂度 – O(N)，其中N是数组的大小。

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