Programme JavaScript pour le sous-tableau non ordonné le plus court Programme JavaScript pour le sous-tableau non ordonné le plus court

L'énoncé du problème nécessite de trouver le sous-tableau non ordonné le plus court dans un tableau d'entiers. En d’autres termes, nous devons déterminer le plus petit sous-tableau dont les éléments ne sont pas triés par ordre croissant ou décroissant. Ce problème peut être résolu de plusieurs manières, mais dans cet article, nous discuterons d'une solution simple mais efficace utilisant JavaScript.

Donc, nous allons d'abord définir ce qu'est un sous-tableau non ordonné, puis comprendre l'énoncé du problème en détail, puis expliquer la solution étape par étape à l'aide d'exemples et d'extraits de code. Après avoir lu cet article, vous comprendrez clairement comment résoudre ce problème en JavaScript. Alors commençons !

Qu'est-ce qu'un sous-tableau non ordonné ?

Un sous-tableau non ordonné est un sous-tableau contigu d'un tableau où les éléments ne sont pas disposés par ordre croissant ou décroissant. En d’autres termes, les éléments du sous-réseau ne sont pas classés par ordre croissant ou décroissant.

Par exemple : [1, 2, 3, 5, 4, 6, 7] est un sous-tableau non ordonné.

Énoncé du problème

Étant donné un tableau d'entiers, nous devons trouver le sous-tableau non ordonné le plus court. En d’autres termes, nous devons trouver le plus petit sous-tableau dont les éléments ne sont pas triés par ordre croissant ou décroissant.

Par exemple, considérons le tableau suivant : const arr = [1, 2, 5, 4, 3, 6, 7]

Dans ce cas, le sous-tableau [5, 4, 3] est le sous-tableau non ordonné le plus court.

Comprenons maintenant l'algorithme pour résoudre ce problème, puis nous commençons à implémenter cet algorithme en utilisant JavaScript.

Algorithme de sous-tableau non ordonné le plus court

Entrée - tableau de n entiers

Sortie - longueur du sous-tableau le plus court non ordonné

Étape 1 - Début de l'initialisation = 0, fin = n-1

ÉTAPE 2 - Parcourez le tableau de gauche à droite et trouvez le premier élément qui est plus grand que son voisin droit. Définissez son index pour démarrer.

ÉTAPE 3 - Parcourez le tableau de droite à gauche et trouvez le premier élément qui est plus petit que son voisin de gauche. Définissez son index pour qu'il se termine.

Étape 4 - Trouvez le plus petit et le plus grand élément du sous-tableau du début à la fin.

ÉTAPE 5 - Parcourez le tableau de 0 à début-1 et trouvez l'index du premier élément qui est supérieur au plus petit élément trouvé à l'étape 4. Placez son index à gauche.

ÉTAPE 6 - Parcourez le tableau de fin+1 à n-1 et trouvez l'index du premier élément qui est plus petit que le plus grand élément trouvé à l'étape 4. Réglez son index à droite.

Étape 7 - La longueur du sous-tableau non ordonné le plus court est (droite - gauche + 1).

Exemple

Dans l'exemple ci-dessous, nous trouvons d'abord l'index de début et de fin du sous-tableau non ordonné en itérant le tableau depuis le début et la fin respectivement. Nous trouvons ensuite les éléments les plus petits et les plus grands du sous-tableau, puis parcourons le tableau respectivement depuis le début et la fin pour trouver les index gauche et droit du sous-tableau.

Enfin, nous renvoyons la longueur du sous-tableau non ordonné le plus court en soustrayant l'index droit de l'index gauche et en ajoutant 1.

function shortestUnorderedSubarray(arr) {
   let n = arr.length;
   let start = 0, end = n - 1;
   // find start index
   for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
         start = i;
         break;
      }
   }
   // find end index
   for (let i = n - 1; i > 0; i--) {
      if (arr[i] < arr[i - 1]) {
         end = i;
         break;
      }
   }
   // find min and max element in subarray
   let min = arr[start], max = arr[start];
   for (let i = start + 1; i <= end; i++) {
      if (arr[i] < min) {
         min = arr[i];
      }
      if (arr[i] > max) {
         max = arr[i];
      }
   }
   // find left index
   let left = 0;
   for (let i = 0; i <= start; i++) {
      if (arr[i] > min) {
         left = i;
         break;
      }
   }
   // find right index
   let right = n - 1;
   for (let i = n - 1; i >= end; i--) {
      if (arr[i] < max) {
         right = i;
         break;
      }
   }
   // return length of shortest un-ordered subarray
   return right - left + 1;
}
// Example usage:
const arr = [1, 2, 5, 4, 3, 6, 7]
console.log("Array:", JSON.stringify(arr))
const len = shortestUnorderedSubarray(arr)
console.log("The length shortest un-ordered subarray: ", len);
// Output: 3, as [5, 4, 3] is the shortest un-ordered subarray with length 3.

Conclusion

Nous avons discuté de toutes les nuances de la façon de résoudre le problème de sous-tableau non ordonné le plus court à l'aide de JavaScript. Nous espérons qu'avec cet article, les utilisateurs pourront facilement trouver et résoudre les problèmes liés aux sous-tableaux non ordonnés dans leur code.

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!