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!