interface Web
js tutoriel
Programme JavaScript pour calculer l'inversion de taille 3 dans un tableau donné
Programme JavaScript pour calculer l'inversion de taille 3 dans un tableau donné
Dans ce tutoriel, nous allons apprendre à calculer l'inversion de taille 3 dans un tableau donné.
Énoncé du problème - On nous donne un tableau de longueur n contenant différentes entrées numériques. Nous devons trouver le nombre total de paires de nombres de taille 3 tels que arr[i] > arr[j] > arr[k], où I
Ici, nous apprendrons d'abord la méthode de la force brute puis nous optimiserons sa complexité temporelle et spatiale.
Utilisez des méthodes de force brute
Dans l'approche par force brute, nous utiliserons trois boucles for imbriquées pour trouver des inversions de nombre de taille 3. La première boucle parcourt de 1 à n-2 éléments et la deuxième boucle parcourt du i-ème élément au n-1-ème élément. Si l'élément précédent est supérieur à l'élément suivant, parcourez le tableau et recherchez l'élément plus petit que l'élément du milieu.
Grammaire
Les utilisateurs peuvent utiliser la méthode de force brute selon la syntaxe ci-dessous pour calculer l'inversion de taille 3 dans un tableau donné.
for ( ) {
for ( ) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
Algorithme
Étape 1 - Parcourez les n-2 premiers éléments à l'aide d'une boucle for.
Étape 2 - Parcourez les éléments m+1 vers len-1 en utilisant une boucle for imbriquée.
Étape 3 - Dans la boucle for imbriquée, vérifiez si array[m] est supérieur à array[n]. Si tel est le cas, parcourez du n+1ème élément au dernier élément.
Étape 4 - Si l'élément au othième index est inférieur à l'élément au nième index, nous pouvons dire que nous avons trouvé une paire inversée valide de taille 3 et incrémenter la variable 'cnt' moins 1.
Étape 5 - Une fois toutes les itérations de la boucle for terminées, renvoyez la valeur de "cnt".
Exemple 1
Dans l'exemple ci-dessous, nous implémentons une méthode de force brute pour trouver le nombre total de paires d'inversion de taille 3.
Dans le tableau donné, l'utilisateur ne peut observer que 2 paires d'inversion dans la sortie. La première paire d'inversions est (10,5,4) et la deuxième paire d'inversions est (20,5,4).
<html>
<body>
<h3> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let len = array.length;
let cnt = 0;
for (let m = 0; m < len - 2; m++) {
for (let n = m + 1; n < len - 1; n++) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Complexité temporelle et spatiale
Complexité temporelle - Puisque nous utilisons trois boucles for imbriquées, la complexité temporelle est O(n^3).
Complexité spatiale - Lorsque nous utilisons un espace constant, la complexité spatiale est O(1).
Utilisez deux boucles for imbriquées
Dans cette méthode, nous utiliserons deux boucles imbriquées. Nous retrouverons le nombre total d’éléments plus petits à droite de l’élément courant, et le nombre total d’éléments plus grands à gauche. Après cela, nous multiplions les deux pour obtenir le nombre total d’inversions pour un nombre spécifique.
Grammaire
Les utilisateurs peuvent suivre la syntaxe ci-dessous pour calculer des inversions de taille 3 en JavaScript à l'aide de deux boucles imbriquées.
for ( ) {
// find a smaller element on the right
for ()
if (array[m] < array[n])
right++;
// find bigger elements on the left
for ()
if (array[m] > array[n])
left++;
cnt += right * left;
}
Algorithme
Étape 1 - Parcourez n éléments du tableau à l'aide d'une boucle for.
Étape 2 - Utilisez une boucle for pour rechercher tous les éléments à droite de l'élément actuel qui sont plus petits que l'élément actuel.
Étape 3 - Utilisez à nouveau la boucle for pour rechercher tous les éléments à gauche de l'élément actuel qui sont plus grands que l'élément actuel.
Étape 4 - Multipliez les valeurs des variables gauche et droite et ajoutez-les à la variable "cnt".
Exemple 2
Dans l'exemple ci-dessous, nous utilisons deux boucles imbriquées pour trouver le nombre total d'inversions de taille 3 comme indiqué dans la méthode ci-dessus. L'utilisateur peut constater que le résultat est le même que dans la première méthode.
<html>
<body>
<h3> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let cnt = 0;
let len = array.length;
// Iterate through every element of the array
for (let m = 0; m < len - 1; m++) {
// count all element that are smaller than arr[m] and at the right to it
let right = 0;
for (let n = m - 1; n >= 0; n--)
if (array[m] < array[n])
right++;
// count all element that are greater than arr[m] and at the left to it
let left = 0;
for (let n = m + 1; n < len; n++)
if (array[m] > array[n])
left++;
// multiply left greater and right smaller elements
cnt += right * left;
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Complexité temporelle et spatiale
Complexité temporelle - Puisque nous utilisons deux boucles imbriquées, la complexité temporelle de la méthode ci-dessus est O(n^2).
Complexité spatiale - Lorsque nous utilisons un espace constant, la complexité spatiale est O(1).
L'utilisateur a appris deux méthodes pour trouver des inversions de nombre de taille 3 dans un tableau donné. Dans la première approche, nous avons résolu le problème en utilisant une approche par force brute, et dans la seconde approche, nous avons encore optimisé la solution pour réduire la complexité temporelle.
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!
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
AI Hentai Generator
Générez AI Hentai gratuitement.
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Sujets chauds
Remplacer les caractères de chaîne en javascript
Mar 11, 2025 am 12:07 AM
Explication détaillée de la méthode de remplacement de la chaîne JavaScript et de la FAQ Cet article explorera deux façons de remplacer les caractères de chaîne dans JavaScript: le code JavaScript interne et le HTML interne pour les pages Web. Remplacer la chaîne dans le code JavaScript Le moyen le plus direct consiste à utiliser la méthode Remplace (): str = str.replace ("trouver", "remplacer"); Cette méthode remplace uniquement la première correspondance. Pour remplacer toutes les correspondances, utilisez une expression régulière et ajoutez le drapeau global G: str = str.replace (/ fi
Tutoriel de configuration de l'API de recherche Google personnalisé
Mar 04, 2025 am 01:06 AM
Ce tutoriel vous montre comment intégrer une API de recherche Google personnalisée dans votre blog ou site Web, offrant une expérience de recherche plus raffinée que les fonctions de recherche de thème WordPress standard. C'est étonnamment facile! Vous pourrez restreindre les recherches à Y
Créez vos propres applications Web Ajax
Mar 09, 2025 am 12:11 AM
Vous voici donc, prêt à tout savoir sur cette chose appelée Ajax. Mais qu'est-ce que c'est exactement? Le terme Ajax fait référence à un regroupement lâche de technologies utilisées pour créer un contenu Web interactif dynamique. Le terme Ajax, inventé à l'origine par Jesse J
Exemple Couleurs Fichier JSON
Mar 03, 2025 am 12:35 AM
Cette série d'articles a été réécrite à la mi-2017 avec des informations à jour et de nouveaux exemples. Dans cet exemple JSON, nous examinerons comment nous pouvons stocker des valeurs simples dans un fichier à l'aide du format JSON. En utilisant la notation de paire de valeurs clés, nous pouvons stocker n'importe quel type
10 Highlighters de syntaxe jQuery
Mar 02, 2025 am 12:32 AM
Améliorez votre présentation de code: 10 surligneurs de syntaxe pour les développeurs Partager des extraits de code sur votre site Web ou votre blog est une pratique courante pour les développeurs. Le choix du bon surligneur de syntaxe peut améliorer considérablement la lisibilité et l'attrait visuel. T
8 Superbes plugins de mise en page JQuery Page
Mar 06, 2025 am 12:48 AM
Tirez parti de jQuery pour les dispositions de page Web sans effort: 8 plugins essentiels JQuery simplifie considérablement la mise en page de la page Web. Cet article met en évidence huit puissants plugins jQuery qui rationalisent le processus, particulièrement utile pour la création de sites Web manuels
10 tutoriels JavaScript & jQuery MVC
Mar 02, 2025 am 01:16 AM
Cet article présente une sélection organisée de plus de 10 didacticiels sur les cadres JavaScript et JQuery Model-View-Controller (MVC), parfait pour augmenter vos compétences en développement Web au cours de la nouvelle année. Ces tutoriels couvrent une gamme de sujets, de Foundatio
Qu'est-ce que & # x27; ceci & # x27; en javascript?
Mar 04, 2025 am 01:15 AM
Points de base Ceci dans JavaScript fait généralement référence à un objet qui "possède" la méthode, mais cela dépend de la façon dont la fonction est appelée. Lorsqu'il n'y a pas d'objet actuel, cela fait référence à l'objet global. Dans un navigateur Web, il est représenté par Window. Lorsque vous appelez une fonction, cela maintient l'objet global; mais lors de l'appel d'un constructeur d'objets ou de l'une de ses méthodes, cela fait référence à une instance de l'objet. Vous pouvez modifier le contexte de ceci en utilisant des méthodes telles que Call (), Appliquer () et Bind (). Ces méthodes appellent la fonction en utilisant la valeur et les paramètres donnés. JavaScript est un excellent langage de programmation. Il y a quelques années, cette phrase était
