排序数组是所有元素都按升序排列的数组。我们给出了一个大小为 N 的数组和一个包含不同整数的数组（这意味着每个整数只出现一次）。我们必须检查数组是否已排序并按顺时针方向旋转。这里，如果数组已排序并旋转，我们必须返回“YES”，否则，我们必须返回“NO”。
注意 - 这里我们讨论的是排序和旋转意味着至少应该存在一个旋转。我们不能将排序数组视为排序和旋转数组。
假设我们已经给出了一个大小为 N 的数组
输入
N = 5 Array = [5, 1, 2, 3, 4]
输出
Yes, the given array is sorted and rotated.
说明
数组是已排序的数组并旋转 1 位
立即学习“Java免费学习笔记（深入）”；
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)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们讨论了如何检查数组是否已排序和旋转。这里我们看到了两种方法，第一种是找到主元（这意味着最小元素），另一种是通过计算相邻反转。两种方法的时间和空间复杂度相同，即 O(N) 和 O(1)分别。
