檢查陣列是否已排序並旋轉的 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)。