Finden Sie das gemeinsame Präfix-Array zweier Arrays

2657. Finden Sie das Präfix Common Array of Two Arrays

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Bitmanipulation

Sie erhalten zwei 0-indizierte ganzzahlige Permutationen A und B der Länge n.

Ein präfixgemeinsames Array von A und B ist ein Array C, so dass C[i] gleich der Anzahl der Zahlen ist, die am oder vor dem Index i in A und B vorhanden sind.

Gibt das präfixgemeinsame Array von A und B zurück.

Eine Folge von n ganzen Zahlen wird als Permutation bezeichnet, wenn sie alle ganzen Zahlen von 1 bis n genau einmal enthält.

Beispiel 1:

• Eingabe: A = [1,3,2,4], B = [3,1,2,4]
• Ausgabe: [0,2,3,4]
• Erklärung: Bei i = 0: Keine Zahl ist üblich, daher ist C[0] = 0.
  • Bei i = 1: 1 und 3 sind in A und B gemeinsam, also ist C[1] = 2.
  • Bei i = 2: 1, 2 und 3 sind in A und B gemeinsam, also ist C[2] = 3.
  • Bei i = 3: 1, 2, 3 und 4 sind in A und B üblich, also ist C[3] = 4.

Beispiel 2:

• Eingabe: A = [2,3,1], B = [3,1,2]
• Ausgabe: [0,1,3]
• Erklärung: Bei i = 0: Keine Zahl ist üblich, daher ist C[0] = 0.
  • Bei i = 1: nur 3 ist in A und B gemeinsam, also C[1] = 1.
  • Bei i = 2: 1, 2 und 3 sind in A und B gemeinsam, also ist C[2] = 3.

Einschränkungen:

• 1
• 1
• Es ist garantiert, dass A und B beide eine Permutation von n ganzen Zahlen sind.

Hinweis:

1. Erwägen Sie, ein Häufigkeitsarray zu führen, das die Anzahl der Vorkommen jeder Zahl bis zum Index i speichert.
2. Wenn eine Zahl zweimal vorkommt, bedeutet das, dass sie sowohl in A als auch in B vorkommt, da es sich bei beiden um Permutationen handelt. Fügen Sie also eins zur Antwort hinzu.

Lösung:

Wir können über die beiden Arrays A und B iterieren und dabei die Zahlen verfolgen, die am oder vor dem aktuellen Index in beiden Arrays aufgetreten sind. Da beide Arrays Permutationen desselben Zahlensatzes sind, können wir zwei Hash-Sets (oder Arrays) verwenden, um zu speichern, welche Zahlen am oder vor dem aktuellen Index in beiden Arrays erschienen sind. Für jeden Index können wir die gemeinsamen Zahlen zählen, die bis zu diesem Zeitpunkt in beiden Arrays aufgetreten sind.

Lösungsansatz:

1. Verwenden Sie zwei Arrays, um das Vorkommen von Zahlen in A und B bis zum Index i zu verfolgen.
2. Überprüfen Sie für jeden Index i, ob sowohl A[i] als auch B[i] zuvor gesehen wurden. Wenn ja, erhöhen Sie die gemeinsame Anzahl.
3. Verwenden Sie ein Häufigkeitsarray, um das Vorhandensein von Zahlen von 1 bis n in beiden Arrays zu verfolgen.

Lassen Sie uns diese Lösung in PHP implementieren: 2657. Finden Sie das Präfix Common Array of Two Arrays

<?php /**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>

Erläuterung:

1. Frequenzarrays: Wir pflegen zwei Frequenzarrays, freqA und freqB, wobei jeder Index eine Zahl in der Permutation darstellt.
   • Wenn wir auf eine Zahl in A[i] oder B[i] stoßen, erhöhen wir den entsprechenden Wert im Häufigkeitsarray.
2. Common Count: Nachdem wir die Häufigkeits-Arrays für A[i] und B[i] aktualisiert haben, prüfen wir für jede Zahl, ob sie in beiden Arrays bis zum Index i vorgekommen ist. Wenn ja, erhöhen wir den commonCount.
3. Ergebnis: Die gemeinsame Anzahl wird im Ergebnisarray für jeden Index gespeichert.

Beispielhafte Vorgehensweise:

Zur Eingabe:

$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• Bei i = 0: Noch keine gemeinsamen Zahlen → C[0] = 0
• Bei i = 1: Zahlen 1 und 3 sind gemeinsam → C[1] = 2
• Bei i = 2: Die Zahlen 1, 2 und 3 sind gemeinsam → C[2] = 3
• Bei i = 3: Die Zahlen 1, 2, 3 und 4 sind gemeinsam → C[3] = 4

Ausgabe: [0, 2, 3, 4]

Zeitkomplexität:

• O(n²⁾: Für jeden Index i überprüfen wir jedes Element von 1 bis n, um zu sehen, ob es gemeinsam ist, wodurch diese Lösung quadratisch in der Zeitkomplexität wird. Dies ist angesichts der Einschränkung n ≤ 50 akzeptabel.

Dies sollte innerhalb der gegebenen Einschränkungen effektiv funktionieren.

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 vonFinden Sie das gemeinsame Präfix-Array zweier Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!