Das schönste Objekt für jede Suchanfrage

2070. Das schönste Objekt für jede Suchanfrage

Schwierigkeit:Mittel

Themen:Array, Binäre Suche, Sortierung

Sie erhalten ein 2D-Integer-Array „items“, wobei items[i] = [price_i, beauty_i] den price und beauty bezeichnet eines Artikels.

Sie erhalten außerdem eine 0-indizierte Ganzzahl-Array-Abfrage. Für jede Abfrage[j] möchten Sie die maximale Schönheit eines Artikels ermitteln, dessen Preis kleiner oder gleich der Abfrage[j] ist. Wenn kein solches Element vorhanden ist, lautet die Antwort auf diese Abfrage 0.

Gibt eine Array-Antwort mit der gleichen Länge wie Abfragen zurück, bei denen Antwort[j] die Antwort auf die j-te Abfrage ist.

Beispiel 1:

• Eingabe: Elemente = [[1,2],[3,2],[2,4],[5,6],[3,5]], Abfragen = [1,2,3 ,4,5,6]
• Ausgabe: [2,4,5,5,6,6]
• Erklärung:
  • Bei Abfragen[0]=1 ist [1,2] der einzige Artikel, dessen Preis <= 1 ist. Daher lautet die Antwort für diese Abfrage 2.
  • Für Abfragen[1]=2 können die Elemente [1,2] und [2,4] berücksichtigt werden.
  • Die maximale Schönheit unter ihnen ist 4.
  • Für Abfragen[2]=3 und Abfragen[3]=4 können folgende Elemente berücksichtigt werden: [1,2], [3,2], [2,4] und [3,5].
  • Die maximale Schönheit unter ihnen ist 5.
  • Bei Abfragen[4]=5 und Abfragen[5]=6 können alle Elemente berücksichtigt werden.
  • Daher ist die Antwort für sie die maximale Schönheit aller Gegenstände, d. h. 6.

Beispiel 2:

• Eingabe: Elemente = [[1,2],[1,2],[1,3],[1,4]], Abfragen = [1]
• Ausgabe: [4]
• Erklärung: Der Preis jedes Artikels ist gleich 1, also wählen wir den Artikel mit der maximalen Schönheit 4.
  • Beachten Sie, dass mehrere Artikel den gleichen Preis und/oder die gleiche Schönheit haben können.

Beispiel 3:

• Eingabe: Elemente = [[10,1000]], Abfragen = [5]
• Ausgabe: [0]
• Erklärung: Kein Artikel hat einen Preis kleiner oder gleich 5, daher kann kein Artikel ausgewählt werden.
  • Daher lautet die Antwort auf die Abfrage 0.

Einschränkungen:

• 1 <= items.length, query.length <= 10⁵
• items[i].length == 2
• 1 <= Preis_i, Schönheit_i, Abfragen[j] <= 10⁹

Hinweis:

1. Können wir die Abfragen in einer intelligenten Reihenfolge verarbeiten, um zu vermeiden, dass dieselben Elemente wiederholt überprüft werden?
2. Wie können wir die Antwort auf eine Anfrage für andere Anfragen nutzen?

Lösung:

Wir können Sortier- und binäre Suchtechniken verwenden. Hier ist der Plan:

Ansatz

1. Sortieren Sie die Artikel nach Preis:

   • Sortieren Sie zunächst die Artikel nach ihrem Preis. Auf diese Weise können wir beim Durchgehen der Artikel die maximale Schönheit verfolgen, die wir bisher für Artikel bis zu einem bestimmten Preis gesehen haben.

2. Sortieren Sie die Abfragen nach ihren ursprünglichen Indizes:

   • Erstellen Sie ein Array von Abfragen gepaart mit ihren ursprünglichen Indizes und sortieren Sie dieses Array dann nach den Abfragewerten.
   • Sortieren hilft, weil wir Anfragen in aufsteigender Preisreihenfolge bearbeiten können und vermeiden, Schönheitswerte wiederholt für niedrigere Preise neu zu berechnen.

3. Elemente und Abfragen gleichzeitig durchlaufen:

   • Verarbeiten Sie jede Abfrage mit zwei Zeigern:
     • Bewegen Sie den Zeiger für jede Abfrage durch Artikel, deren Preis kleiner oder gleich dem Preis der Abfrage ist.
     • Verfolgen Sie die maximale Schönheit, während Sie diese Elemente durchgehen, und verwenden Sie diesen Wert, um die aktuelle Abfrage zu beantworten.
     • Dadurch wird vermieden, dass Elemente wiederholt auf mehrere Abfragen überprüft werden.

4. Ergebnisse speichern und zurückgeben:

   • Speichern Sie nach der Verarbeitung das maximale Schönheitsergebnis für jede Abfrage basierend auf dem ursprünglichen Index, um die Reihenfolge beizubehalten.
   • Gibt das Antwortarray zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2070. Schönster Artikel für jede Suchanfrage

  
  
  Erläuterung:




Elemente und Abfragen sortieren: Dies ermöglicht eine effiziente Verarbeitung ohne redundante Berechnungen.

Zwei-Zeiger-Technik: Das einmalige Durchgehen von Elementen pro Abfrage vermeidet übermäßige Berechnungen.

MaxBeauty verfolgen: Wir aktualisieren maxBeauty schrittweise, sodass jede Abfrage auf die bisher höchste Schönheit zugreifen kann.



  
  
  Komplexität




Zeitkomplexität: O(n log n m log m) zum Sortieren von Elementen und Abfragen und O(n m) für die Verarbeitung, wobei n die Länge der Elemente und m die Länge der Abfragen ist.

Raumkomplexität: O(m) zum Speichern der Ergebnisse.


Diese Lösung ist effizient und erfüllt die Einschränkungen des Problems.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        


Das obige ist der detaillierte Inhalt vonDas schönste Objekt für jede Suchanfrage. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!