632. Plus petite gamme couvrant des éléments de k listes

difficulté: dur

sujets: array, table hash, fenêtre gourmand, glissante, tri, tas (file d'attente de priorité)

Vous avez k listes d'entiers triés dans Ordre non décroissante . Recherchez la plus petite gamme qui inclut au moins un numéro de chacune des K listes.

nous définissons la plage [a, b] est plus petite que la plage [c, d] si b - a ou a

Exemple 1:

• entrée: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• output: [20,24]
• Explication:
  • Liste 1: [4, 10, 15, 24,26], 24 est dans la plage [20,24].
  • list 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]]
• output: [1,1]

contraintes:

• nums.length == k
• 1
• 1
• - 10 ⁵ 5
• nums [i] est trié dans Ordre non décroissant.

Solution:

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

Approche

1. initialisation min-heap : utilisez un mine-heap pour stocker les éléments actuels de chacune des K listes. Chaque entrée de tas sera un tuple contenant la valeur, l'index de la liste d'où il vient et l'index de l'élément de cette liste.
2. Suivi de valeur max : 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 précédemment enregistrée.
   • Passez à l'élément suivant de la liste à partir de laquelle l'élément minimum a été pris. Mettez à jour la valeur maximale et ajoutez le nouvel élément au tas.
4. terminaison : le processus se termine lorsque toute liste est épuisée.

implémentons cette solution dans php: 632. Plus petite gamme couvrant des éléments de k listes

Explication:

1. HEAP Initialisation :
   • 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.
2. Traitement du tas :
   • Extraire 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 le maxvalue si le nouvel élément est plus grand.
   • Mettez à jour la plus petite plage chaque fois que la différence entre le maxvalue et le minValue est plus petite que la plage précédemment enregistrée.
3. Terminaison:
   • La boucle s'arrête lorsqu'une liste est à court d'éléments, car nous ne pouvons plus inclure toutes les listes dans la gamme.

Analyse de complexité

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

Cette solution trouve efficacement la plus petite plage qui inclut au moins un numéro de chacune des K triés.

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

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

• linkedIn
• github