数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究JavaScript 程序检查是否可以通过旋转数组进行排序
旋转数组意味着将每个索引的元素（不包括一端）移动到右旋转的下一个索引和左旋转的上一个索引。对于右旋转，第零个索引取最后一个索引的值，反之亦然，对于左旋转。排序数组意味着所有元素都按正确的升序排列。我们将实现正确的代码，并进行解释以及时间和空间复杂度讨论。
示例
Input: 5 6 9 10 2 3 3 4 Output: Yes
说明：我们可以将给定数组旋转 4 次以获得排序数组。
First Rotation: 4 5 6 9 10 2 3 3 Second Rotation: 3 4 5 6 9 10 2 3 Third Rotation: 3 3 4 5 6 9 10 2 Fourth Rotation: 2 3 3 4 5 6 9 10
朴素方法
在这种方法中，主要思想是，在旋转次数等于数组长度后，我们将获得相同的数组。因此，我们将旋转数组等于其长度的次数，并且对于每次旋转，我们将使用双指针和交换方法。在每次旋转时，我们将检查当前数组是否已排序。
示例
// function to rotate the given array
function rotate(arr){
var l = 0;
var r = arr.length-1;
while(l < r){
arr[l] += arr[r];
arr[r] = arr[l]-arr[r];
arr[l] = arr[l]-arr[r];
l++;
}
return arr;
}
// function to check if the given array is increasing or not
function increasing(arr){
// getting the size of array
var len = arr.length
// traversing over the array
for(var i = 1; i < len; i++){
if(arr[i] < arr[i-1]){
return false;
}
}
return true;
}
// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
var k = arr.length
while(k--){
if(increasing(arr)){
console.log("The given array can be sorted after " + (arr.length-k-1) + " rotations");
return
}
arr = rotate(arr);
}
console.log("The given array cannot be sorted");
}
//defining the given array
var arr = [5, 6, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);
// calling the function
check(arr);
输出
Given array is: 5,6,9,10,2,3,3,4 The given array can be sorted after 4 rotations
时间和空间复杂度
上述代码的时间复杂度为 O(N*N)，其中 N 是数组的大小。我们正在旋转数组 N 次，每次旋转需要 N 次移动。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
有效方法
先前代码的时间复杂度很高，可以通过观察来降低，如果给定数组已排序或分为两部分，则第二部分的元素小于或等于第一部分，并且两部分本身都是排序的。
示例
// function to check if the given array is increasing or not
function increasing(arr){
// getting the size of the array
var len = arr.length
// traversing over the array
var i = 0;
for(var i = 1; i < len; i++){
if(arr[i] < arr[i-1]){
break;
}
}
if(i == len) return true;
i++;
for(; i< len; i++){
if(arr[i] < arr[i-1]){
return false;
}
}
return arr[len-1] <= arr[0];
}
// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
if(increasing(arr)){
console.log("The given array can be sorted after ");
}
else{
console.log("The given array cannot be sorted");
}
}
//defining the given array
var arr = [5, 4, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);
// calling the function
check(arr);
输出
Given array is: 5,4,9,10,2,3,3,4 The given array cannot be sorted
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是数组的大小。我们只遍历数组一次。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们实现了 JavaScript 代码来检查我们是否可以通过旋转其元素来对元素进行排序。旋转数组意味着将每个索引的元素（不包括一端）移动到右旋转的下一个索引和左旋转的上一个索引。我们实现了两种方法，一种时间复杂度为 O(N*N)，另一种为 O(N)。
更新于： 2023年4月13日
72 次查看
广告