JavaScript程序：检查数组是否已排序并旋转

已排序数组是指所有元素按递增顺序排列的数组。我们已经得到了一个大小为N的数组和一个包含不同整数的数组（这意味着每个整数仅出现一次）。我们必须检查数组是否顺时针排序并旋转。如果数组已排序并旋转，则返回“YES”，否则返回“NO”。

注意 – 在这里，我们讨论的是已排序并旋转的意思至少应该存在一个旋转。我们不能将已排序的数组视为已排序并旋转数组。

假设我们给出一个大小为N的数组，如下所示：

输入

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

输出

是的，给定的数组是已排序并旋转的。

解释

该数组是一个已排序并旋转了1个位置的数组。

已排序数组= [1, 2, 3, 4, 5]
将上面排序的数组旋转1个位置，我们得到= [5, 1, 2, 3, 4]

1个位置排序和旋转的数组与输入的数组匹配，因此输出为是。

输入

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

输出

不，给定的数组不是已排序并旋转的数组。

解释

给定的数组不是已排序并旋转的数组

已排序数组= [1, 2, 3, 4, 5, 6]
将上面排序的数组旋转1个位置，我们得到= [6, 1, 2, 3, 4, 5]
将上面排序的数组旋转2个位置，我们得到= [5, 6, 1, 2, 3, 4]
将上面排序的数组旋转3个位置，我们得到= [4, 5, 6, 1, 2, 3]
将上面排序的数组旋转4个位置，我们得到= [3, 4, 5, 6, 1, 2]
将上面排序的数组旋转5个位置，我们得到= [2, 3, 4, 5, 6, 1]

上面的任何已排序并旋转的数组都不符合输入的数组，因此答案为No。

方法

在这里，我们将讨论两种方法。接下来让我们看看它们的下面部分-

方法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;
      }
   }

   if (arr[len - 1] > arr[0]){
      return false;
   }
   return true;
} 

var arr = [5, 6, 1, 2, 3, 4];
var result = check(arr);
if (result == true){
   console.log("Yes, the given array is sorted and rotated.");
} else {
   console.log("No, the given array is not sorted and rotated array.");
}

方法2：检查数组的第一个元素是不是最小元素

这种方法的想法是在找到第一个比最后一个数字大的值之前，将数组的第一个元素递增。

示例

function check(arr){
   var len = arr.length;

   // Find the number of times the array is rotated 
   var min = arr[0], min_index = -1;
   for(var i = 0; i < len; i++){
      if(min > arr[i]){
         min = arr[i];
         min_index = i;
      }
   }

   // The original array itself sorted in increasing order
   if(min_index == -1){
      return true;
   }

   // Copying the sorted part of array at its end 
   var temp = new Array(len);
   var j = 0;
   for(var i = min_index; i < len; i++){
      temp[j] = arr[i];
      j++;
   }
   for(var i = 0; i < min_index; i++){
      temp[j] = arr[i];
      j++;
   }
   temp[j] = temp[0];  

   // Testing if the copy is the same as the one given 
   var count = 0;
   for(var i = 0; i < len; i++){
      if(temp[i] == arr[i]){
         count++;
      }
   }
   if(count == len){
      return true;
   } else {
      return false;
   }
}

var arr1 = [2, 3, 4, 5, 6, 1];
var result1 = check(arr1);
if (result1 == true){
   console.log("Yes, the given array is sorted and rotated.");
} else {
   console.log("No, the given array is not sorted and rotated array.");
}

var arr2 = [6, 5, 1, 2, 3, 4];
var result2 = check(arr2);
if (result2 == true){
   console.log("Yes, the given array is sorted and rotated.");
} else {
   console.log("No, the given array is not sorted and rotated array.");
}

if (arr[i] < arr[i - 1]){
         return false;
      }
   }

   // 检查数组的最后一个元素是否小于第一个元素
   if(arr[len-1] > arr[0]){
      return false;
   }
   else{
      return true;
   }
}

// 定义数组
var arr = [5, 1, 2, 3, 4];
console.log("给定的数组是: ")
console.log(arr);

// 调用函数
if(check(arr)){
   console.log("是的，给定的数组是已排序并旋转的");
}
else{
   console.log("不，给定的数组不是已排序并旋转的数组")
}

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

空间复杂度- O(1)，因为我们不使用任何其他空间。

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

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

示例

// 检查给定的数组是否已排序并旋转的函数
function check(arr){
   var len = arr.length;
   var count = 0; // 变量计算相邻逆序对的数量

   // 遍历数组以查找第一个元素小于第二个元素的次数
   for(var i = 1; i < len; i++){
      if (arr[i] < arr[i-1]){
         count++;
      }
   }

   // 检查数组的最后一个元素是否小于第一个元素
   // 并且逆序对必须等于1
   if(arr[len-1] > arr[0] || count != 1){
      return false;
   }
   else{
      return true;
   }
}

// 定义数组
var arr = [5, 1, 2, 3, 4];
console.log("给定的数组是: ")
console.log(arr);

// 调用函数
if(check(arr)){
   console.log("是的，给定的数组是已排序并旋转的");
}
else{
   console.log("不，给定的数组不是已排序并旋转的数组")
}

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

空间复杂度- O(1)，因为我们不使用任何其他空间。