排序数组是所有元素都按升序排列的数组。我们给出了一个大小为 n 的数组和一个包含不同整数的数组（这意味着每个整数只出现一次）。我们必须检查数组是否已排序并按顺时针方向旋转。这里，如果数组已排序并旋转，我们必须返回“yes”，否则，我们必须返回“no”。
注意 - 这里我们讨论的是排序和旋转意味着至少应该存在一个旋转。我们不能将排序数组视为排序和旋转数组。
假设我们已经给出了一个大小为 n 的数组
输入n = 5array = [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 = 6array = [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 functionif(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 functionif(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)分别。
以上就是javascript程序：检查数组是否已排序并旋转的详细内容。