Maximale Anzahl auswählbarer Ganzzahlen aus einem Bereich I

2554. Maximale Anzahl von Ganzzahlen zur Auswahl aus einem Bereich I

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Binäre Suche, Gierig, Sortieren

Sie erhalten ein Ganzzahl-Array banned und zwei Ganzzahlen n und maxSum. Sie wählen eine bestimmte Anzahl von Ganzzahlen gemäß den folgenden Regeln aus:

• Die gewählten ganzen Zahlen müssen im Bereich [1, n] liegen.
• Jede ganze Zahl kann höchstens einmal ausgewählt werden.
• Die ausgewählten Ganzzahlen sollten nicht im Array verboten sein.
• Die Summe der ausgewählten Ganzzahlen sollte maxSum nicht überschreiten.

Gib die maximale Anzahl an Ganzzahlen zurück, die Sie gemäß den genannten Regeln auswählen können.

Beispiel 1:

• Eingabe:banned = [1,6,5], n = 5, maxSum = 6
• Ausgabe: 2
• Erklärung: Sie können die ganzen Zahlen 2 und 4 wählen.
  • 2 und 4 stammen aus dem Bereich [1, 5], beide tauchten nicht in Banned auf und ihre Summe beträgt 6, was maxSum nicht überschreitet.

Beispiel 2:

• Eingabe:banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
• Ausgabe: 0
• Erklärung:Sie können keine ganze Zahl auswählen, während Sie die genannten Bedingungen befolgen.

Beispiel 3:

• Eingabe:banned = [11], n = 7, maxSum = 50
• Ausgabe: 7
• Erklärung: Sie können die ganzen Zahlen 1, 2, 3, 4, 5, 6 und 7 auswählen.
  • Sie stammen aus dem Bereich [1, 7], alle sind nicht in Banned enthalten, und ihre Summe beträgt 28, was maxSum nicht übersteigt.

Einschränkungen:

• 1 <= banned.length <= 10⁴
• 1 <= verboten[i], n <= 10⁴
• 1 <= maxSum <= 10⁹

Hinweis:

1. Behalten Sie die verbotenen Zahlen, die kleiner als n sind, in einem Satz.
2. Schleifen Sie die Zahlen von 1 bis n durch und verwenden Sie sie, wenn die Zahl nicht gesperrt ist.
3. Fügen Sie weiterhin Zahlen hinzu, solange diese nicht verboten sind und ihre Summe weniger als k beträgt.

Lösung:

Wir können einen gierigen Ansatz verwenden, bei dem wir über die Zahlen von 1 bis n iterieren, die verbotenen Zahlen überspringen und die gültigen Zahlen (die nicht im verbotenen Array enthalten sind) so lange zu einer laufenden Summe addieren, bis wir die maxSum erreichen.

Hier ist die Schritt-für-Schritt-Lösung:

Schritte:

1. Verbotenes Array in einen Satz für schnelle Suchvorgänge konvertieren: Mit array_flip() kann das gesperrte Array in einen Satz für Suchvorgänge mit durchschnittlicher O(1)-Zeitkomplexität konvertiert werden.
2. Iterieren Sie von 1 bis n:Überprüfen Sie jede Zahl. Wenn sie nicht in der verbotenen Menge enthalten ist und wenn die Addition maxSum nicht überschreitet, addieren Sie sie zur Summe und erhöhen Sie die Anzahl.
3. Hören Sie auf, die nächste Zahl zu addieren, die maxSum überschreitet: Da das Ziel darin besteht, die Anzahl der ausgewählten ganzen Zahlen zu maximieren, ohne die Summe zu überschreiten, stellt dieser gierige Ansatz sicher, dass wir zuerst die kleinsten verfügbaren Zahlen nehmen.

Ansatz:

1. Gesperrte Nummern ausschließen: Wir verfolgen die gesperrten Nummern in einem Satz (oder einem assoziativen Array) für eine schnelle Suche.
2. Gierige Auswahl: Beginnen Sie mit der Auswahl von Zahlen von 1 bis n in aufsteigender Reihenfolge, da wir so die Anzahl der ausgewählten ganzen Zahlen maximieren können. Jedes Mal, wenn wir eine Zahl auswählen, addieren wir sie zur Summe und prüfen, ob sie maxSum überschreitet. Wenn ja, hören Sie auf.
3. Effizienzüberlegungen: Da wir über Zahlen von 1 bis n iterieren und prüfen, ob sich jede in der verbotenen Menge befindet (was in konstanter Zeit erfolgen kann), läuft der Ansatz in linearer Zeit relativ zu n und dem Größe der Sperrliste.

Lassen Sie uns diese Lösung in PHP implementieren: 2554. Maximale Anzahl von Ganzzahlen zur Auswahl aus einem Bereich I

  
  
  Erläuterung:



Verbotenes Array in Satz umwandeln:


Wir verwenden array_flip($banned), um einen Satz aus dem gesperrten Array zu erstellen, der es O(1)-Suchvorgängen ermöglicht, zu überprüfen, ob eine Zahl gesperrt ist.

Iteriere von 1 bis n:


Wir iterieren durch Zahlen von 1 bis n. Für jede Zahl:


Wenn die Nummer nicht im gesperrten Satz enthalten ist (überprüft mit isset($bannedSet[$i])),
Und wenn die Addition der Zahl zur Summe maxSum nicht überschreitet,
Wir schließen diese Zahl ein und aktualisieren die Summe und Zählung.


Zählung zurückgeben:


Nach der Schleife geben wir die Anzahl der ausgewählten Ganzzahlen zurück ($count).
$bannedSet = array_flip($banned);: Dies wandelt die gesperrte Liste in einen Satz (assoziatives Array) für schnelle Suchvorgänge um.
for ($i = 1; $i <= $n; $i ): Wir iterieren über alle ganzen Zahlen von 1 bis n.
if (isset($bannedSet[$i])) { continue; }: Dies prüft, ob die aktuelle Nummer im gesperrten Satz enthalten ist. Wenn ja, überspringen wir es.
if ($sum $i > $maxSum) { break; }: Wenn das Hinzufügen der aktuellen Zahl maxSum überschreitet, stoppen wir den Vorgang.
$sum = $i; $count ;: Wenn die Zahl gültig ist und die Addition maxSum nicht überschreitet, schließen wir sie in unsere Summe ein und erhöhen die Anzahl.



  
  
  Zeitkomplexität:



Die Erstellung des verbotenen Satzes (array_flip) ist O(b), wobei b die Länge des verbotenen Arrays ist.
Die Schleife wird n-mal durchlaufen (für Zahlen von 1 bis n), und jede Suche in der verbotenen Menge dauert O(1) Zeit. Die zeitliche Komplexität der Schleife beträgt also O(n).
Daher beträgt die Gesamtzeitkomplexität O(n b), was angesichts der Problembeschränkungen effizient ist.



  
  
  Beispielhafte Vorgehensweise:


Zur Eingabe:



Eingabe 1:banned = [1, 6, 5], n = 5, maxSum = 6


Wir erstellen den verbotenen Satz: {1, 5, 6}.
Wir durchlaufen die Nummern 1 bis 5:


1 ist gesperrt, überspringen Sie es.
2 ist nicht verboten, addiere es zur Summe (Summe = 2, Anzahl = 1).
3 ist nicht verboten, addieren Sie es zur Summe (Summe = 5, Anzahl = 2).
4 ist nicht verboten, aber das Hinzufügen zur Summe würde maxSum (5 4 = 9) überschreiten, also überspringen Sie es.





Das Ergebnis ist 2.







Eingabe 2:banned = [1, 2, 3, 4, 5, 6, 7], n = 8, maxSum = 1


Alle Zahlen von 1 bis 7 sind gesperrt, daher können keine gültigen Zahlen ausgewählt werden.
Das Ergebnis ist 0.







Eingabe 3:banned = [11], n = 7, maxSum = 50


Die einzige verbotene Zahl ist 11, die außerhalb des Bereichs 1 bis 7 liegt.
Wir können alle Zahlen von 1 bis 7 auswählen und ihre Summe beträgt 28, was kleiner als maxSum ist.
Das Ergebnis ist 7.







Diese Lösung löst das Problem effizient innerhalb der gegebenen Einschränkungen.

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 vonMaximale Anzahl auswählbarer Ganzzahlen aus einem Bereich I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!