Programme JavaScript : vérifiez si le tableau est trié et faites-le pivoter

Un tableau trié est un tableau dans lequel tous les éléments sont classés par ordre croissant. On nous donne un tableau de taille N et un tableau contenant des entiers distincts (ce qui signifie que chaque entier n'apparaît qu'une seule fois). Nous devons vérifier si le tableau est trié et tourné dans le sens des aiguilles d'une montre. Ici, si le tableau est trié et pivoté, nous devons renvoyer "OUI", sinon nous devons renvoyer "NON".

Remarque - Nous parlons ici de tri et de rotation, ce qui signifie qu'il doit y avoir au moins une rotation. Nous ne pouvons pas traiter un tableau trié comme un tableau trié et pivoté.

Supposons que nous ayons reçu un tableau de taille N

Entrez

N = 5
Array = [5, 1, 2, 3, 4]

Sortie

Yes, the given array is sorted and rotated. 

Instructions

Le tableau est un tableau trié et pivoté de 1 bit

Sorted array = [1, 2, 3, 4, 5]
Rotated above sorted array by 1 place, we get = [5, 1, 2, 3, 4]

Le tableau trié par 1 position et pivoté correspond au tableau d'entrée, donc la sortie est "oui".

Entrez

N = 6
Array = [6, 5, 1, 2, 3, 4]

Sortie

No, the given array is not sorted and rotated array. 

Instructions

Le tableau donné est un tableau non trié et pivoté

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]

Ni les tableaux triés ni ceux pivotés ci-dessus ne correspondent au tableau d'entrée, la réponse est donc non.

Méthode

Ici, nous discuterons de deux méthodes. Voyons-les dans les sections ci-dessous -

Méthode 1 : Vérifiez si le tableau est trié et pivoté en trouvant l'élément pivot (nombre minimum)

L'idée de cette méthode est que nous trouverons le nombre minimum et si notre tableau est trié et pivoté, les valeurs avant et après le nombre minimum doivent être triées.

Exemple

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

Complexité temporelle - O(N), où N est la taille du tableau.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire.

Méthode 2 : Vérifiez si le tableau est trié et pivoté en calculant les inversions adjacentes

L'idée de cette méthode est que nous allons parcourir le tableau et vérifier si l'élément précédent est inférieur à l'élément actuel. Pour un tableau trié et pivoté, le nombre doit être 1 si l'élément précédent est supérieur à l'élément actuel, sinon le tableau n'est pas trié et pivoté.

Exemple

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

Complexité temporelle - O(N), où N est la taille du tableau.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire.

Conclusion

Dans ce didacticiel, nous avons expliqué comment vérifier si un tableau est trié et pivoté. Ici, nous voyons deux méthodes, la première consiste à trouver le pivot (c'est-à-dire le plus petit élément) et l'autre consiste à calculer les inversions adjacentes. La complexité temporelle et spatiale des deux méthodes est la même, c'est-à-dire respectivement O(N) et 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!