Le plus bel objet pour chaque requête

2070. Le plus bel article pour chaque requête

Difficulté :Moyen

Sujets : Tableau, recherche binaire, tri

Vous recevez un tableau d'entiers 2D items où items[i] = [price_i, beauty_i] désigne le prix et beauté d'un article respectivement.

Vous recevez également des requêtes sur un tableau d'entiers indexés à 0. Pour chaque requête[j], vous souhaitez déterminer la beauté maximale d'un article dont le prix est inférieur ou égal aux requêtes[j]. Si aucun élément de ce type n'existe, alors la réponse à cette requête est 0.

Renvoyer un tableau de réponse de la même longueur que les requêtes où réponse[j] est la réponse à la jième requête.

Exemple 1 :

• Entrée : éléments = [[1,2],[3,2],[2,4],[5,6],[3,5]], requêtes = [1,2,3 ,4,5,6]
• Sortie : [2,4,5,5,6,6]
• Explication :
  • Pour les requêtes[0]=1, [1,2] est le seul article dont le prix est <= 1. Par conséquent, la réponse à cette requête est 2.
  • Pour les requêtes[1]=2, les éléments qui peuvent être considérés sont [1,2] et [2,4].
  • La beauté maximale parmi eux est de 4.
  • Pour les requêtes[2]=3 et les requêtes[3]=4, les éléments qui peuvent être pris en compte sont [1,2], [3,2], [2,4] et [3,5].
  • La beauté maximale parmi eux est de 5.
  • Pour les requêtes[4]=5 et les requêtes[5]=6, tous les éléments peuvent être pris en compte.
  • Par conséquent, la réponse pour eux est la beauté maximale de tous les objets, c'est-à-dire 6.

Exemple 2 :

• Entrée : éléments = [[1,2],[1,2],[1,3],[1,4]], requêtes = [1]
• Sortie : [4]
• Explication : Le prix de chaque article est égal à 1, nous choisissons donc l'article avec la beauté maximale 4.
  • Notez que plusieurs articles peuvent avoir le même prix et/ou la même beauté.

Exemple 3 :

• Entrée : éléments = [[10,1000]], requêtes = [5]
• Sortie : [0]
• Explication : Aucun article n'a un prix inférieur ou égal à 5, aucun article ne peut donc être choisi.
  • Par conséquent, la réponse à la requête est 0.

Contraintes :

• 1 <= items.length, queries.length <= 10⁵
• articles[i].length == 2
• 1 <= prix_i, beauté_i, requêtes[j] <= 10⁹

Indice :

1. Pouvons-nous traiter les requêtes dans un ordre intelligent pour éviter de vérifier à plusieurs reprises les mêmes éléments ?
2. Comment pouvons-nous utiliser la réponse à une requête pour d'autres requêtes ?

Solution :

Nous pouvons utiliser des techniques de tri et de recherche binaire. Voici le plan :

Approche

1. Trier les articles par prix :

   • Tout d’abord, triez les articles selon leur prix. De cette façon, au fur et à mesure que nous parcourons les articles, nous pouvons garder une trace de la beauté maximale observée jusqu'à présent pour les articles jusqu'à un prix donné.

2. Trier les requêtes avec leurs indices d'origine :

   • Créez un tableau de requêtes associées à leurs indices d'origine, puis triez ce tableau en fonction des valeurs de requête.
   • Le tri est utile car nous pouvons traiter les requêtes par ordre croissant de prix et éviter de recalculer les valeurs de beauté pour des prix inférieurs à plusieurs reprises.

3. Parcourir simultanément les éléments et les requêtes :

   • À l'aide de deux pointeurs, traitez chaque requête :
     • Pour chaque requête, déplacez le pointeur sur les articles dont le prix est inférieur ou égal au prix de la requête.
     • Suivez la beauté maximale au fur et à mesure que vous parcourez ces éléments et utilisez cette valeur pour répondre à la requête en cours.
     • Cela évite de vérifier à plusieurs reprises les éléments pour plusieurs requêtes.

4. Résultats du magasin et des retours :

   • Une fois traité, stockez le résultat de beauté maximum pour chaque requête en fonction de l'index d'origine pour maintenir l'ordre.
   • Renvoyer le tableau de réponses.

Implémentons cette solution en PHP : 2070. Le plus bel article pour chaque requête

  
  
  Explication:




Tri des éléments et des requêtes : Cela permet un traitement efficace sans calculs redondants.

Technique à deux pointeurs : parcourir les éléments une seule fois pour chaque requête évite des calculs excessifs.

Suivre maxBeauty : Nous mettons à jour maxBeauty progressivement, permettant à chaque requête d'accéder à la plus haute beauté vue jusqu'à présent.



  
  
  Complexité




Complexité temporelle : O(n log n m log m) pour trier les éléments et les requêtes, et O(n m) pour le traitement, où n est la longueur des éléments et m est la longueur des requêtes.

Complexité spatiale : O(m) pour stocker les résultats.


Cette solution est efficace et répond aux contraintes du problème.

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!