Spezial-Array II

3152. Spezial-Array II

Schwierigkeit:Mittel

Themen:Array, Binäre Suche, Präfixsumme

Ein Array gilt als besonders, wenn jedes Paar seiner benachbarten Elemente zwei Zahlen mit unterschiedlicher Parität enthält.

Sie erhalten ein Array ganzzahliger Zahlen und eine 2D-Ganzzahlmatrix-Abfrage, wobei Ihre Aufgabe darin besteht, dies für Abfragen[i] = [von_i, bis_i] zu überprüfen Unterarray¹ nums[von_i..bis_i] ist etwas Besonderes oder nicht.

Gib ein Array boolescher Antworten zurück, so dass Antwort[i] wahr ist, wenn nums[from_i..to_i] speziell ist.

Beispiel 1:

• Eingabe: Zahlen = [3,4,1,2,6], Abfragen = [[0,4]]
• Ausgabe: [false]
• Erklärung: Das Subarray ist [3,4,1,2,6]. 2 und 6 sind beide gerade.

Beispiel 2:

• Eingabe: Zahlen = [4,3,1,6], Abfragen = [[0,2],[2,3]]
• Ausgabe: [falsch, wahr]
• Erklärung:

1. Das Subarray ist [4,3,1]. 3 und 1 sind beide ungerade. Die Antwort auf diese Frage ist also falsch.
2. Das Subarray ist [1,6]. Es gibt nur ein Paar: (1,6) und es enthält Zahlen mit unterschiedlicher Parität. Die Antwort auf diese Frage ist also wahr.

Einschränkungen:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵
• 1 <= query.length <= 10⁵
• queries[i].length == 2
• 0 <= query[i][0] <= query[i][1] <= nums.length - 1

Hinweis:

1. Versuchen Sie, das Array in einige nicht überschnittene kontinuierliche spezielle Unterarrays aufzuteilen.
2. Überprüfen Sie bei jeder Abfrage, ob sich das erste und das letzte Element dieser Abfrage im selben Subarray befinden oder nicht.

Lösung:

Wir müssen feststellen, ob ein Subarray von Zahlen „speziell“ ist, d. h. jedes Paar benachbarter Elemente im Subarray muss eine andere Parität haben (eines muss ungerade und das andere muss gerade sein).

Ansatz:

1. Paritätsübergänge identifizieren: Wir können das Array vorverarbeiten, um Positionen zu markieren, an denen sich die Parität ändert. Zum Beispiel:
   • 0 stellt eine gerade Zahl dar.
   • 1 stellt eine ungerade Zahl dar.

Die Idee besteht darin, alle Positionen zu identifizieren, an denen benachbarte Elemente unterschiedliche Parität haben. Dadurch können wir effizient feststellen, ob ein Subarray etwas Besonderes ist, indem wir prüfen, ob die Positionen in der Abfrage Teil desselben „speziellen“ Blocks sind.

1. Vorverarbeitung:
   Erstellen Sie ein binäres Array parity_change, in dem jedes Element 1 ist, wenn die benachbarten Elemente unterschiedliche Parität haben, andernfalls 0. Zum Beispiel:

   • Wenn nums[i] und nums[i 1] unterschiedliche Parität haben, setzen Sie parity_change[i] = 1, andernfalls 0.

2. Präfix-Summen-Array:
   Erstellen Sie ein Präfixsummen-Array prefix_sum, in dem jeder Eintrag am Index i die kumulative Anzahl der Paritätsübergänge bis zu diesem Index darstellt. Dies hilft, schnell zu überprüfen, ob alle Paare innerhalb eines Subarrays unterschiedliche Parität haben.

3. Abfrageverarbeitung:
   Überprüfen Sie für jede Abfrage [von, bis], ob es eine Position im Bereich [von, bis-1] gibt, an der sich die Parität nicht ändert. Dies kann durch Überprüfen der Differenz in den Präfixsummenwerten erfolgen: prefix_sum[to] - prefix_sum[from].

Lassen Sie uns diese Lösung in PHP implementieren: 3152. Spezial-Array II

<?php
/**
 * @param Integer[] $nums
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function specialArray($nums, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3,4,1,2,6];
$queries1 = [[0, 4]];
print_r(specialArray($nums1, $queries1)); // [false]

$nums2 = [4,3,1,6];
$queries2 = [[0, 2], [2, 3]];
print_r(specialArray($nums2, $queries2)); // [false, true]
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li><p><strong>Paritätsübergänge vorverarbeiten:</strong><br>
Wir berechnen parity_change[i] = 1, wenn die Elemente nums[i] und nums[i 1] unterschiedliche Parität haben. Andernfalls setzen wir es auf 0.</p></li>
<li><p><strong>Präfix-Summen-Array:</strong><br>
Die prefix_sum[i] speichert die kumulative Anzahl der Paritätsübergänge vom Anfang des Arrays bis zum Index i. Dadurch können wir mithilfe der Formel berechnen, wie viele Übergänge in einem beliebigen Subarray [von, nach] in konstanter Zeit stattgefunden haben:<br>
</p></li>
</ol>

<pre class="brush:php;toolbar:false">   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. Abfrageauswertung: Wenn für jede Abfrage die Anzahl der Übergänge gleich der Länge des Subarrays minus 1 ist, ist das Subarray etwas Besonderes und wir geben „true“ zurück. Andernfalls geben wir false zurück.

Zeitkomplexität:

• Die Vorverarbeitung der Paritätsübergänge erfordert O(n).
• Der Aufbau des Präfix-Summen-Arrays erfordert O(n).
• Jede Abfrage kann in O(1) mit dem Präfix-Summen-Array beantwortet werden.
• Daher beträgt die Gesamtzeitkomplexität O(n q), wobei n die Länge des Arrays und q die Anzahl der Abfragen ist.

Diese Lösung bewältigt die Problembeschränkungen effizient mit einem optimierten Ansatz.

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

1. Subarray Ein Subarray ist eine zusammenhängende Folge von Elementen innerhalb eines Arrays. ↩

Das obige ist der detaillierte Inhalt vonSpezial-Array II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!