Trouver le score d'un tableau après avoir marqué tous les éléments

2593. Trouver le score d'un tableau après avoir marqué tous les éléments

Difficulté :Moyen

Sujets : Tas (file d'attente prioritaire), tri, tableau, simulation, table de hachage, ensemble ordonné, carte ordonnée, gourmand, pile monotone, fenêtre coulissante, deux pointeurs, pile, file d'attente, manipulation de bits, Diviser pour mieux régner, programmation dynamique, liste doublement chaînée, flux de données, tri par base, retour en arrière, masque de bits, arbre, conception, fonction de hachage, Chaîne, itérateur, tri par comptage, liste chaînée

Vous recevez un tableau numérique composé d'entiers positifs.

En commençant par score = 0, appliquez l'algorithme suivant :

• Choisissez le plus petit entier du tableau qui n'est pas marqué. En cas d'égalité, choisissez celui avec le plus petit indice.
• Ajoutez la valeur de l'entier choisi pour marquer.
• Marquer l'élément choisi et ses deux éléments adjacents s'ils existent.
• Répétez jusqu'à ce que tous les éléments du tableau soient marqués.

Renvoyez le score que vous obtenez après avoir appliqué l'algorithme ci-dessus.

Exemple 1 :

• Entrée : nums = [2,1,3,4,5,2]
• Sortie :7
• Explication : Nous marquons les éléments comme suit :
  • 1 est le plus petit élément non marqué, nous le marquons donc ainsi que ses deux éléments adjacents : [2,1,3,4,5,2].
  • 2 est le plus petit élément non marqué, nous le marquons donc ainsi que son élément adjacent gauche : [2,1,3,4,5,2].
  • 4 est le seul élément non marqué restant, nous le marquons donc : [2,1,3,4,5,2].
  • Notre score est 1 2 4 = 7.

Exemple 2 :

• Entrée : nums = [2,3,5,1,3,2]
• Sortie : 5
• Explication : Nous marquons les éléments comme suit :
  • 1 est le plus petit élément non marqué, nous le marquons donc ainsi que ses deux éléments adjacents : [2,3,5,1,3,2].
  • 2 est le plus petit élément non marqué, puisqu'il y en a deux, on choisit celui le plus à gauche, on marque donc celui à l'index 0 et son élément adjacent droit : [2,3,5,1,3, 2].
  • 2 est le seul élément non marqué restant, nous le marquons donc : [2,3,5,1,3,2].
  • Notre score est 1 2 2 = 5.

Contraintes :

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁶

Indice :

1. Essayez de simuler le processus de marquage des éléments et de leurs adjacents.
2. S'il y a un élément qui a déjà été marqué, alors vous le sautez.

Solution :

Nous pouvons simuler efficacement le processus de marquage en utilisant un tableau trié ou une file d'attente prioritaire pour garder une trace du plus petit élément non marqué. Nous pouvons donc utiliser l'approche suivante :

Plan:

1. Analyse des entrées : lisez les numéros du tableau et initialisez les variables pour le score et l'état de notation.
2. Tas (file d'attente prioritaire) :
   • Utilisez un min-heap pour extraire efficacement le plus petit élément non marqué à chaque étape.
   • Insérez chaque élément dans le tas avec son index (valeur, index) pour gérer les liens en fonction du plus petit index.
3. Éléments de marquage :
   • Maintenez un tableau marqué pour savoir si un élément et ses éléments adjacents sont marqués.
   • Lors du traitement d'un élément du tas, ignorez-le s'il est déjà marqué.
   • Marquez l'élément courant et ses deux éléments adjacents (s'ils existent).
   • Ajoutez la valeur de l'élément actuel au score.
4. Répéter : Continuez jusqu'à ce que tous les éléments soient marqués.
5. Sortie : renvoie le score accumulé.

Implémentons cette solution en PHP : 2593. Trouver le score d'un tableau après avoir marqué tous les éléments

  
  
  Explication:




Construction en tas :


La fonction usort trie le tableau en fonction des valeurs et par index lorsque les valeurs sont liées.
Cela garantit que nous traitons toujours le plus petit élément non marqué avec le plus petit indice.



Logique de marquage :


Pour chaque élément non marqué, nous le marquons ainsi que ses éléments adjacents à l'aide du tableau marqué.
Cela garantit que nous ignorons efficacement les éléments précédemment marqués.



Complexité temporelle :


Tri du tas : O(n log n)

Traitement du tas : O(n)

Global : O(n log n), ce qui est efficace pour les contraintes données.



Complexité spatiale :


Tableau marqué : O(n)

Tas : O(n)

Total : O(n)





Cette solution répond aux contraintes et fonctionne efficacement pour les gros intrants.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
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!