Kürzestes Subarray mit OR von mindestens K II

3097. Kürzestes Subarray mit ODER mindestens K II

Schwierigkeit:Mittel

Themen: Array, Bitmanipulation, Schiebefenster

Sie erhalten eine Array-Anzahl von nichtnegativen Ganzzahlen und eine Ganzzahl k.

Ein Array heißt speziell, wenn das bitweise ODER aller seiner Elemente mindestens k.

Gib die Länge des kürzesten speziellen nicht leeren Subarrays¹ von Zahlen zurück, oder gib -1 zurück, wenn kein spezielles Subarray vorhanden ist.

Beispiel 1:

• Eingabe: nums = [1,2,3], k = 2
• Ausgabe: 1
• Erklärung: Das Subarray [3] hat den ODER-Wert 3. Daher geben wir 1 zurück.

Beispiel 2:

• Eingabe: nums = [2,1,8], k = 10
• Ausgabe: 3
• Erklärung: Das Subarray [2,1,8] hat den ODER-Wert 11. Daher geben wir 3 zurück.

Beispiel 3:

• Eingabe: nums = [1,2], k = 0
• Ausgabe: 1
• Erklärung: Das Subarray [1] hat den ODER-Wert 1. Daher geben wir 1 zurück.

Einschränkungen:

• 1 <= nums.length <= 2 * 10⁵
• 0 <= nums[i] <= 10⁹
• 0 <= k <= 10⁹

Hinweis:

1. Für jedes Nums[i] können wir das bitweise ODER-Ergebnis jedes Subarrays beibehalten, das damit endet.
2. Die Eigenschaft des bitweisen ODER besteht darin, dass es niemals irgendwelche Bits zurücksetzt und nur neue Bits setzt
3. Die Anzahl der unterschiedlichen Ergebnisse für jedes nums[i] beträgt also höchstens die Anzahl der Bits 32.

Lösung:

Wir können einen Schiebefenster-Ansatz in Kombination mit Bitmanipulation verwenden, um die ODER-Verknüpfung von Elementen im Fenster zu verfolgen.

Planen:

1. Schiebefenster-Ansatz: Mit zwei Zeigern über das Array iterieren und dabei ein Unterarray beibehalten, dessen ODER-Wert überprüft wird.
2. Bitweises ODER: Die ODER-Operation akkumuliert Werte. Es reduziert niemals das Ergebnis (d. h. wenn ein Bit einmal auf 1 gesetzt ist, kann es nicht mehr zurückgesetzt werden). Das heißt, wenn wir das Fenster erweitern, erhöht sich der OR-Wert nur oder bleibt gleich.
3. Effizienz: Wir können eine Deque (doppelte Warteschlange) verwenden, um die Indizes der Subarrays zu verwalten. Dadurch können wir das Fenster effizient verschieben und gleichzeitig die minimale Subarray-Länge im Auge behalten.

Schritte:

1. Durchlaufen Sie das Array und pflegen Sie für jedes Element ein laufendes ODER.
2. Überprüfen Sie für jedes Element, ob das OR größer oder gleich k ist. Wenn dies der Fall ist, versuchen Sie, das Fenster von der linken Seite aus zu verkleinern.
3. Das Schiebefenster sollte effizient verschoben werden, indem der OR-Wert in einer Deque-Struktur verfolgt wird, um ein konstantes Schieben und Verkleinern der Zeit zu ermöglichen.

Lassen Sie uns diese Lösung in PHP implementieren: 3097. Kürzestes Subarray mit OR mindestens K II

minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>





  
  
  Erläuterung:




minimumSubarrayLength-Methode:


Ans auf einen unmöglich hohen Wert initialisieren ($n 1).
Verwenden Sie zwei Zeiger l (links) und r (rechts), um das Fenster zu erweitern und zu verkleinern.
Berechnen Sie das ODER des Subarrays, wenn Sie das Fenster mit orNum erweitern, und verkleinern Sie es mit undoOrNum, wenn Sie es verkleinern.
Immer wenn das ODER-Ergebnis k erreicht oder überschreitet, prüfen Sie, ob die aktuelle Fenstergröße kleiner als ans ist.



orNum- und undoOrNum-Methoden:



orNum-Methode: Fügt Bits zum kumulativen ODER hinzu, indem das Zählarray aktualisiert wird. Wenn ein Bit im Fenster neu gesetzt wird (was bedeutet, dass count[i] 1 wird), wird dieses Bit zu ors.
 hinzugefügt

undoOrNum-Methode: Entfernt Bits aus dem kumulativen OR, wenn das Fenster nach links verschoben wird. Wenn in keiner der Zahlen im Fenster ein Bit mehr gesetzt ist (was bedeutet, dass count[i] 0 wird), wird dieses Bit aus ors entfernt.



Zeitkomplexität:


Die zeitliche Komplexität beträgt O(n), da jeder Index höchstens einmal zur Deque hinzugefügt und daraus entfernt wird.

n ist die Länge des Eingabearrays.




4*Zeitkomplexität*:


Die Raumkomplexität beträgt O(n) zum Speichern des Präfix-OR-Arrays und der Deque.


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








Subarray: Ein Subarray ist eine zusammenhängende nicht leere Folge von Elementen innerhalb eines Arrays. ↩





          

            
  

            
        
Das obige ist der detaillierte Inhalt vonKürzestes Subarray mit OR von mindestens K II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!