Le programme JavaScript vérifie si le tableau peut être augmenté ou diminué en le faisant pivoter

La rotation d'un tableau signifie supposer que le tableau est un tableau circulaire. Chaque rotation fait pivoter les éléments du tableau vers la gauche ou la droite d'un indice, et les éléments à une extrémité peuvent prendre la valeur de l'autre extrémité. . Un tableau croissant signifie que chaque élément sera supérieur ou égal à son élément précédent, un tableau décroissant signifie que chaque élément sera inférieur ou égal à l'élément précédent.

Dans ce problème, on nous donne un tableau et nous pouvons faire pivoter le tableau vers la gauche ou la droite et nous devons savoir si nous pouvons faire augmenter ou diminuer le tableau après une certaine rotation (qui peut être nulle). p>

Méthode naïve

Dans cette méthode, nous ferons pivoter le tableau et pour chaque rotation, nous vérifierons si le tableau actuel augmente ou diminue.

Exemple

Dans l'exemple ci-dessous, nous vérifions si le tableau donné peut être augmenté ou diminué en le faisant pivoter. Vous trouverez ci-dessous l’entrée et la sortie attendue.

Entrée : arr = [3, 4, 5, 6, 1, 2]

Résultat attendu : Oui

Entrée : arr = [5, 1, 6, 2, 5, 3]

Résultat attendu : Non

Exemple

// 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");
}

Sortie

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

La complexité temporelle du code ci-dessus est O(N*N) et la complexité spatiale est O(1).

Méthode efficace

Dans le tableau précédent, nous avons vérifié si le tableau augmentait ou diminuait à chaque rotation, dans cette méthode, nous vérifierons partiellement l'augmentation ou la diminution du tableau.

Exemple

// 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");
}

Sortie

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

La complexité temporelle du code ci-dessus est O(N) et la complexité spatiale est O(1).

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript qui vérifie si un tableau donné peut être augmenté ou diminué en le faisant pivoter. Nous avons implémenté deux méthodes avec une complexité temporelle O(N*N) et O(N), et une complexité spatiale toutes deux O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!