Größte Kombination mit bitweisem UND größer als Null

2275. Größte Kombination mit bitweisem UND größer als Null

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Bitmanipulation, Zählen

Das bitweise UND eines Arrays nums ist das bitweise UND aller ganzen Zahlen in nums.

• Zum Beispiel ist für Zahlen = [1, 5, 3] das bitweise UND gleich 1 & 5 & 3 = 1.
• Außerdem ist für nums = [7] das bitweise UND 7.

Sie erhalten eine Reihe positiver Ganzzahlkandidaten. Bewerten Sie das bitweise UND jeder Kombination der Anzahl der Kandidaten. Jede Zahl in Kandidaten darf in jeder Kombination nur einmal verwendet werden.

Gibt die Größe der größten Kombination von Kandidaten mit einem bitweisen UND größer als 0 zurück.

Beispiel 1:

• Eingabe: Kandidaten = [16,17,71,62,12,24,14]
• Ausgabe: 4
• Erklärung: Die Kombination [16,17,62,24] hat ein bitweises UND von 16 & 17 & 62 & 24 = 16 > 0.
  • Die Größe der Kombination beträgt 4.
  • Es kann gezeigt werden, dass keine Kombination mit einer Größe größer als 4 ein bitweises UND größer als 0 hat.
  • Beachten Sie, dass mehr als eine Kombination die größte Größe haben kann.
  • Zum Beispiel hat die Kombination [62,12,24,14] ein bitweises UND von 62 & 12 & 24 & 14 = 8 > 0.

Beispiel 2:

• Eingabe: Kandidaten = [8,8]
• Ausgabe: 2
• Erklärung: Die größte Kombination [8,8] hat ein bitweises UND von 8 & 8 = 8 > 0.
  • Die Größe der Kombination beträgt 2, also geben wir 2 zurück.

Einschränkungen:

• 1 <= Candidates.length <= 10⁵
• 1 <= Kandidaten[i] <= 10⁷

Hinweis:

1. Damit das bitweise UND größer als Null ist, sollte mindestens ein Bit für jede Zahl in der Kombination 1 sein.
2. Die Kandidaten sind 24 Bit lang, daher können wir für jede Bitposition die Größe der größten Kombination berechnen, sodass das bitweise UND an dieser Bitposition eine 1 hat.

Lösung:

Wir müssen uns auf die Identifizierung von Zahlengruppen konzentrieren, bei denen mindestens eine Bitposition in ihrer binären Darstellung über alle Zahlen in der Kombination hinweg gesetzt (1) bleibt.

Lösungsübersicht

1. Bitanalyse: Da jede Zahl in Kandidaten durch eine Binärzahl mit bis zu 24 Bits dargestellt werden kann (als 1 <= Kandidaten[i] <= 10^7), Wir müssen nur jede Bitposition von 0 bis 23 untersuchen.

2. Zähle gesetzte Bits an jeder Position: Zählen Sie für jede Bitposition, wie viele Zahlen in Kandidaten dieses Bit auf 1 gesetzt haben. Wenn mehrere Zahlen ein Bit an derselben Position teilen, könnten sie dies tun Bilden Sie möglicherweise eine Kombination mit einem bitweisen UND größer als Null an dieser Bitposition.

3. Finden Sie die größte Anzahl: Die größte Anzahl von Zahlen mit einem gesetzten Bit an einer bestimmten Position ist die Antwort, da sie die größtmögliche Kombination darstellt, bei der das bitweise UND-Ergebnis größer als ist Null.

Beispiel

Kandidaten berücksichtigen = [16, 17, 71, 62, 12, 24, 14]:

• Wandeln Sie jede Zahl in eine Binärzahl um und analysieren Sie die Bitpositionen.
• Zählen Sie, wie oft jedes Bit in allen Zahlen gesetzt ist.
• Ermitteln Sie die maximale Anzahl über alle Bitpositionen.

Lassen Sie uns diese Lösung in PHP implementieren: 2275. Größte Kombination mit bitweisem UND größer als Null

  
  
  Erläuterung:




Jede Bitposition durchlaufen: Wir durchlaufen jede Bitposition von 0 bis 23.

Zahlen mit gesetztem Bit zählen: Zählen Sie für jede Position, wie viele Zahlen in Kandidaten dieses bestimmte Bit gesetzt haben.

Maximale Kombinationsgröße aktualisieren: Verfolgen Sie die höchste Anzahl über alle Bitpositionen hinweg.

Ergebnis zurückgeben: Das Ergebnis ist die größte Kombinationsgröße mit einem bitweisen UND größer als Null, je nach Bedarf.



  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n x 24) = O(n), wobei n die Anzahl von ist Elemente in Kandidaten, da wir für jede Zahl 24 Operationen (eine für jede Bitposition) durchführen.

Raumkomplexität: O(1), da wir nur eine feste Menge an zusätzlichem Raum nutzen.


Dieser Ansatz ist effizient genug, um die Eingabegrößenbeschränkung (candidates.length <= 105) zu bewältigen.

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 vonGrößte Kombination mit bitweisem UND größer als Null. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!