排序陣列是所有元素都按升序排列的陣列。我們給出了一個大小為 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)分別。
以上是JavaScript程式：檢查陣列是否已排序並旋轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！
