. La plus petite plage couvrant les éléments des listes K

632. La plus petite gamme couvrant les éléments des listes K

Difficulté : Difficile

Sujets : Tableau, table de hachage, gourmand, fenêtre coulissante, tri, tas (file d'attente prioritaire)

Vous avez k listes d'entiers triés dans ordre non décroissant. Trouvez la la plus petite plage qui comprend au moins un numéro de chacune des k listes.

Nous définissons que la plage [a, b] est plus petite que la plage [c, d] si b - a < d - c ou a < c si b - a == d - c.

Exemple 1 :

• Entrée : nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
• Sortie : [20,24]
• Explication :
  • Liste 1 : [4, 10, 15, 24,26], 24 est dans la plage [20,24].
  • Liste 2 : [0, 9, 12, 20], 20 est dans la plage [20,24].
  • Liste 3 : [5, 18, 22, 30], 22 est dans la plage [20,24].

Exemple 2 :

• Entrée : nums = [[1,2,3],[1,2,3],[1,2,3]]
• Sortie : [1,1]

Contraintes :

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10⁵ <= nums[i][j] <= 10⁵
• nums[i] est trié dans un ordre non décroissant.

Solution :

Nous pouvons utiliser un min-heap (ou file d'attente prioritaire) pour suivre le plus petit élément de chaque liste tout en maintenant une fenêtre glissante pour trouver la plus petite plage comprenant au moins un élément de chaque liste.

Approche

1. Initialisation Min-Heap : utilisez un min-heap pour stocker les éléments actuels de chacune des k listes. Chaque entrée du tas sera un tuple contenant la valeur, l'index de la liste d'où elle provient et l'index de l'élément dans cette liste.
2. Suivi de la valeur maximale : gardez une trace de la valeur maximale dans la fenêtre actuelle. Ceci est important car la plage est déterminée par la différence entre le plus petit élément (du tas) et le maximum actuel.
3. Itérer jusqu'à la fin des listes : Pour chaque itération :
   • Extraire l'élément minimum du tas.
   • Mettez à jour la plage si la plage actuelle [min_value, max_value] est plus petite que la plus petite plage enregistrée précédemment.
   • Passer à l'élément suivant de la liste à partir duquel l'élément minimum a été extrait. Mettez à jour la valeur maximale et ajoutez le nouvel élément au tas.
4. Résiliation : Le processus se termine lorsqu'une liste est épuisée.

Implémentons cette solution en PHP : 632. La plus petite gamme couvrant les éléments des listes K

  
  
  Explication:




Initialisation du tas :


Le tas initial contient le premier élément de chaque liste. Nous gardons également une trace de l'élément maximum parmi les premiers éléments.



Traitement du tas :


Extrayez l'élément minimum du tas, puis essayez d'étendre la plage en ajoutant l'élément suivant de la même liste (si disponible).
Après avoir ajouté un nouvel élément au tas, mettez à jour maxValue si le nouvel élément est plus grand.
Mettez à jour la plus petite plage chaque fois que la différence entre maxValue et minValue est inférieure à la plage précédemment enregistrée.



Résiliation :


La boucle s'arrête lorsqu'une liste manque d'éléments, car nous ne pouvons plus inclure toutes les listes dans la plage.





  
  
  Analyse de complexité




Complexité temporelle : O(n * log k), où n est le nombre total d'éléments dans toutes les listes et k est le nombre de listes. La complexité vient de l'insertion et de la suppression d'éléments du tas.

Complexité spatiale : O(k) pour stocker des éléments dans le tas.


Cette solution trouve efficacement la plus petite plage comprenant au moins un numéro de chacune des k listes triées.

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!