Programme JavaScript pour maximiser les éléments en utilisant un autre tableau

Dans cet article, nous allons implémenter un programme JavaScript pour maximiser les éléments en utilisant un autre tableau. Nous avons deux tableaux et devons sélectionner certains éléments du deuxième tableau et remplacer les éléments du premier tableau. Nous verrons le code complet qui implémente les concepts qui seront abordés.

Introduction au problème

Dans ce problème, nous avons deux tableaux et nous devons rendre tous les éléments du premier tableau les plus grands possibles ou simplement nous devons faire en sorte que la somme de tous les éléments du premier tableau soit la plus grande. Nous pouvons sélectionner des éléments du deuxième tableau, mais le fait est que nous ne devons sélectionner un élément du deuxième tableau qu'une seule fois, après quoi nous ne pouvons sélectionner qu'un autre élément. Par exemple -

Nous avons deux tableaux -

Array1: 1 2 3 4 5 
Array2: 5 6 2 1 9

Nous pouvons voir que de nombreux éléments du deuxième tableau sont plus grands que ceux présents dans le premier tableau.

Nous pouvons choisir 9 au lieu de 3, 6 au lieu de 2 et 5 au lieu de 1. Cela fait ressembler le tableau final à ceci -

5 6 9 4 5 

Nous verrons deux méthodes, toutes deux implémentées en triant un tableau et deux pointeurs, mais la seule différence est l'endroit où nous sélectionnerons le pointeur.

Méthode

Nous avons vu l'exemple ci-dessus, à partir duquel nous pouvons voir que nous pouvons échanger les petits éléments du premier tableau avec le plus grand élément du deuxième tableau.

• Étape 1 - Tout d'abord, nous allons trier les deux tableaux par ordre croissant, puis inverser le deuxième tableau afin qu'il soit trié par ordre décroissant.

• Étape 2 - Nous conserverons deux pointeurs vers le premier index des deux tableaux.

• Étape 3 - Puisque le pointeur du premier élément pointe vers le plus petit nombre, nous pouvons échanger ce nombre avec le plus grand nombre du deuxième tableau.

• Étape 4 - À chaque itération, nous échangerons les deux pointeurs de tableau et incrémenterons les pointeurs.

• Étape 5 - Si l'élément de l'index actuel du premier tableau devient plus grand par rapport à l'élément du deuxième tableau, alors nous pouvons arrêter les étapes suivantes.

• Étape 6 - Enfin, nous imprimerons les éléments du tableau.

Exemple

// function to find the maximum array
function maximumArray(array1, array2){
   var len1 = array1.length
   var len2 = array2.length
   
   // sorting the elements of both arrays
   array1.sort()
   array2.sort()
   
   // reversing the arrays
   array1.reverse()
   array2.reverse()
   
   // traversing over the arrays
   var ptr1 = 0
   var ptr2 = 0
   var ptr3 = 0
   
   // creating new array to store the answer
   var ans = new Array(len1);
   while(ptr3 < len1){
      if(ptr2 == len2){
         while(ptr3 != len1){
            ans[ptr3] = array1[ptr1];
            ptr3++;
            ptr1++;
         }
      }
      else if(array1[ptr1] > array2[ptr2]){
         ans[ptr3] = array1[ptr1];
         ptr1++;
      } else {
         ans[ptr3] = array2[ptr2];
         ptr2++;
      }
      ptr3++;
   }
   console.log("The final array is: ")
   console.log(ans)
}
// declaring arrays
array1 = [1, 2, 4, 5, 3]
array2 = [5, 6, 2, 1, 9]

// calling the function
maximumArray(array1,array2)

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*log(N)), où N est la taille du tableau donné et le facteur logarithmique ici est dû à la fonction de tri que nous utilisons pour trier le tableau.

Nous utilisons un tableau supplémentaire pour stocker les éléments, ce qui rend la complexité spatiale O(N), mais le tableau est nécessaire pour stocker sa réponse, qui peut ou non être considérée comme un espace supplémentaire.

Méthode de tri direct

Dans la méthode précédente, nous avons trié les éléments du tableau puis utilisé deux méthodes de pointeur, mais il existe une méthode directe à l'aide de laquelle nous pouvons le faire simplement -

• En utilisant le mot-clé new et le mot-clé Array, nous créerons un nouveau tableau dont la taille est la somme ou la longueur des deux tableaux donnés.

• Nous remplissons un par un tous les éléments des deux tableaux donnés dans le nouveau tableau.

• Nous trierons le tableau nouvellement créé pour organiser les éléments par ordre croissant.

• Tous les plus grands éléments sont présents à la fin et on peut les obtenir facilement.

Exemple

// function to find the maximum array
function maximumArray(array1, array2){
   var len1 = array1.length
   var len2 = array2.length
   var ans = new Array(len1+len2);
   for(var i = 0; i<len1; i++){
      ans[i] = array1[i];
   }
   for(var i = 0; i< len2; i++){
      ans[i+len1] = array2[i];
   }
   ans.sort();
   for(var i = 0;i<len1;i++){
      array1[i] = ans[len2+len1-i-1];
   }
   console.log("The final array is: ")
   console.log(array1)
}

// declaring arrays
array1 = [1, 2, 4, 5, 3]
array2 = [5, 6, 2, 1, 9]
// calling the function
maximumArray(array1,array2)

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*log(N)), où N est la taille du tableau donné et le facteur logarithmique ici est dû à la fonction de tri que nous utilisons pour trier le tableau.

Nous utilisons un tableau supplémentaire pour stocker les éléments, ce qui rend la complexité spatiale O(N).

Conclusion

Dans le tutoriel ci-dessus, nous avons implémenté un programme JavaScript qui maximise les éléments en utilisant un autre tableau. Nous avons deux tableaux et devons sélectionner certains éléments du deuxième tableau et remplacer les éléments du premier tableau. Nous avons vu que les deux méthodes utilisent la notion de tri. Une méthode avec deux pointeurs prend du temps O(N*log(N)) et de l'espace O(1), tandis que l'autre méthode prend le même temps mais de l'espace O(N).

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!