数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查数组是否已排序并旋转的 JavaScript 程序
排序数组是指所有元素都按升序排列的数组。我们给定一个大小为 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)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们讨论了如何检查数组是否已排序并旋转。在这里，我们看到了两种方法，第一种是通过查找枢纽元素（即最小元素），另一种是通过计算相邻反转。这两种方法的时间和空间复杂度相同，即分别为 O(N) 和 O(1)。
更新于： 2023年4月21日
210 次查看
广告