JavaScript 程式檢查是否可以透過旋轉數組來增加或減少數組

數組的旋轉是指將數組假設為圓形數組，每次旋轉時將數組的元素向左或向右旋轉一個索引，一端的元素可以採用另一端的值。遞增數組意味著每個元素將大於或等於其前一個元素，遞減數組意味著每個元素將小於或等於前一個元素。

在這個問題中，我們給定一個數組，我們可以向左或向右旋轉數組，我們必須找出在一定的旋轉（可能為零）之後是否可以使數組增加或減少。 p>

天真的方法

在這種方法中，我們將旋轉數組，並且對於每次旋轉，我們將檢查當前數組是增加還是減少。

範例

在下面的範例中，我們檢查是否可以透過旋轉給定陣列來增加或減少它。以下是輸入和預期輸出。

輸入：arr = [3, 4, 5, 6, 1, 2]

預期輸出：是

輸入：arr = [ 5, 1, 6, 2, 5, 3 ]

預期輸出：否

範例

// 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 if the given array is decreasing or not
function decreasing(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) || decreasing(arr)){
         return true;
      }
      arr = rotate(arr);
   }
   return false;
}

// defining the arr's
var arr1 = [3, 4, 5, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

輸出

The given array is: 
[ 3, 4, 5, 6, 1, 2 ]
Yes, after some rotations given array can be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

上述程式碼的時間複雜度為O(N*N)，空間複雜度為O(1)。

高效的方法

在前面的陣列中，我們檢查了每次旋轉陣列是否增加或減少，在這種方法中，我們將部分檢查增加或減少的陣列。

範例

// 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
   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 if the given array is decreasing or not
function decreasing(arr){

   // getting the size of 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) || decreasing(arr)){
      return true;
   }
   else{
      return false;
   }
}

// defining the arr's
var arr1 = [3, 4, 7, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

輸出

The given array is: 
[ 3, 4, 7, 6, 1, 2 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

上述程式碼的時間複雜度為O(N)，空間複雜度為O(1)。

結論

在本教程中，我們實作了一個 JavaScript 程序，用於檢查是否可以透過旋轉給定數組來增加或減少它。我們實作了兩種時間複雜度為 O(N*N) 和 O(N) 的方法，且空間複雜度均為 O(1)。

以上是JavaScript 程式檢查是否可以透過旋轉數組來增加或減少數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！