Primzahlsubtraktionsoperation

2601. Primzahlsubtraktionsoperation

Schwierigkeit:Mittel

Themen: Array, Mathematik, Binäre Suche, Greedy, Zahlentheorie

Sie erhalten ein 0-indiziertes ganzzahliges Array mit Zahlen der Länge n.

Sie können den folgenden Vorgang beliebig oft ausführen:

• Wählen Sie einen Index i, den Sie zuvor noch nicht ausgewählt haben, und wählen Sie eine Primzahl p streng kleiner als nums[i] aus, und subtrahieren Sie dann p von nums[i].

Gib true zurück, wenn du nums mithilfe der obigen Operation zu einem strikt ansteigenden Array machen kannst, andernfalls false.

Ein streng ansteigendes Array ist ein Array, dessen jedes Element streng größer als sein vorhergehendes Element ist.

Beispiel 1:

• Eingabe: nums = [4,9,6,10]
• Ausgabe:wahr
• Erklärung: In der ersten Operation: Wählen Sie i = 0 und p = 3 und subtrahieren Sie dann 3 von nums[0], sodass nums zu [1,9,6,10] wird.
  • In der zweiten Operation: i = 1, p = 7, subtrahiere 7 von nums[1], sodass nums gleich [1,2,6,10] wird.
  • Nach der zweiten Operation wird nums in streng aufsteigender Reihenfolge sortiert, sodass die Antwort wahr ist.

Beispiel 2:

• Eingabe: nums = [6,8,11,12]
• Ausgabe:wahr
• Erklärung:Anfangs ist nums in streng aufsteigender Reihenfolge sortiert, sodass wir keine Operationen durchführen müssen.

Beispiel 3:

• Eingabe: nums = [5,8,3]
• Ausgabe:false
• Erklärung: Es kann bewiesen werden, dass es keine Möglichkeit gibt, Operationen durchzuführen, um Zahlen in streng aufsteigender Reihenfolge zu sortieren, daher ist die Antwort falsch.

Einschränkungen:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

Hinweis:

1. Überlegen Sie, ob wir viele Primzahlen von nums[i] subtrahieren müssen. Welche Primzahl ist optimaler?
2. Die optimalste Primzahl zum Subtrahieren von nums[i] ist diejenige, die nums[i] so klein wie möglich und größer als nums[i-1] macht.

Lösung:

Wir müssen den Algorithmus aufschlüsseln und an die PHP-Syntax und -Funktionalität anpassen. Die Lösung umfasst im Wesentlichen die folgenden Schritte:

1. Erstellen von Primzahlen (Sieb des Eratosthenes):Erzeugen Sie eine Liste aller Primzahlen bis zum maximal möglichen Wert in Zahlen (1000).
2. Primzahl-Subtraktionsoperation:Überprüfen Sie für jede Zahl in Zahlen, ob wir eine Primzahl subtrahieren können, um das Array streng wachsend zu machen.
3. Binäre Suche nach Primzahlen: Verwenden Sie eine binäre Suche, um die größte Primzahl zu finden, die kleiner als die aktuelle Zahl ist und die die Folge dennoch streng aufsteigend halten würde.

Lassen Sie uns diese Lösung in PHP implementieren: 2601. Primzahlsubtraktionsoperation

primeSubOperation([4, 9, 6, 10]) ? 'true' : 'false';  // Output: true
echo $solution->primeSubOperation([6, 8, 11, 12]) ? 'true' : 'false'; // Output: true
echo $solution->primeSubOperation([5, 8, 3]) ? 'true' : 'false';      // Output: false
?>





  
  
  Erläuterung:




primeSubOperation: Durchläuft jedes Element in Zahlen und prüft, ob wir jedes Element durch Subtrahieren einer entsprechenden Primzahl größer als das vorherige machen können.


Wir verwenden $this->findLargestPrimeLessThan, um die größte Primzahl kleiner als num zu finden – prevNum.
Wenn eine solche Primzahl existiert, subtrahieren wir sie von der aktuellen Zahl.
Wenn nach dem Subtrahieren der Primzahl die aktuelle Zahl nicht größer als prevNum ist, geben wir false zurück.
Andernfalls aktualisieren wir prevNum auf die aktuelle Nummer.


SiebEratosthenes: Erzeugt alle Primzahlen bis 1000 mit dem Sieb des Eratosthenes und gibt sie als Array zurück.
findLargestPrimeLessThan: Verwendet die binäre Suche, um die größte Primzahl zu finden, die kleiner als ein gegebener Grenzwert ist, und stellt so sicher, dass wir die optimale Primzahl für die Subtraktion finden.



  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n . √m), wobei n die Länge von nums und m ist ist der Maximalwert eines Elements in Nums (hier m = 1000).

Raumkomplexität: O(m), wird zum Speichern der Liste der Primzahlen bis 1000 verwendet.


Diese Lösung gibt „true“ oder „false“ zurück, je nachdem, ob es möglich ist, Zahlen durch Ausführen der beschriebenen Primzahlsubtraktionsoperationen streng ansteigend zu machen.

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 vonPrimzahlsubtraktionsoperation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!