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

王林转载: 2023-08-23 23:37:02 350浏览

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

注意 - 这里我们讨论的是排序和旋转意味着至少应该存在一个旋转。我们不能将排序数组视为排序和旋转数组。

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

输入

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

输出

Yes, the given array is sorted and rotated.

说明

数组是已排序的数组并旋转 1 位

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

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

输入

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)，因为我们没有使用任何额外的空间。