Erste vollständig bemalte Zeile oder Spalte

2661. Erste vollständig bemalte Zeile oder Spalte

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Matrix

Sie erhalten ein 0-indiziertes ganzzahliges Array arr und eine m x n ganzzahlige Matrix mat. arr und mat enthalten beide alle die ganzen Zahlen im Bereich [1, m * n].

Gehen Sie jeden Index i in arr beginnend mit Index 0 durch und malen Sie die Zelle in mat, die die Ganzzahl arr[i] enthält.

Gib den kleinsten Index i zurück, bei dem entweder eine Zeile oder eine Spalte vollständig in Mat gezeichnet wird.

Beispiel 1:

• Eingabe: arr = [1,3,4,2], mat = [[1,4],[2,3]]
• Ausgabe: 2
• Erklärung: Die Züge werden der Reihe nach angezeigt und sowohl die erste Zeile als auch die zweite Spalte der Matrix werden bei arr[2] vollständig gezeichnet.

Beispiel 2:

• Eingabe: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[ 8,7,9]]
• Ausgabe: 3
• Erklärung: Die zweite Spalte wird bei arr[3] vollständig gezeichnet.

Einschränkungen:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 5
• 1 5
• 1
• Alle ganzen Zahlen von arr sind einzigartig.
• Alle ganzen Zahlen von mat sind eindeutig.

Hinweis:

1. Können wir ein Frequenzarray verwenden?
2. Verarbeiten Sie die Positionen der Werte in der Matrix vor.
3. Durchlaufen Sie das Array und erhöhen Sie die entsprechende Zeilen- und Spaltenfrequenz mithilfe der vorverarbeiteten Positionen.
4. Wenn die Zeilenhäufigkeit gleich der Anzahl der Spalten wird oder umgekehrt, wird der aktuelle Index zurückgegeben.

Lösung:

Wir können diesen Schritten folgen:

Ansatz

1. Positionen von Elementen vorverarbeiten:

   • Zuerst müssen wir die Positionen der Elemente in der Matrix speichern. Wir können ein Wörterbuch (position_map) erstellen, das jeden Wert in der Matrix seiner (Zeile, Spalte) Position zuordnet.

2. Frequenz-Arrays:

   • Wir benötigen zwei Frequenzarrays: eines für die Zeilen und eines für die Spalten.
   • Während wir das arr-Array durchgehen, erhöhen wir die Häufigkeit der jeweiligen Zeile und Spalte für jedes Element.

3. Auf vollständige Zeile oder Spalte prüfen:

   • Überprüfen Sie nach jedem Inkrement, ob eine Zeile oder Spalte vollständig gezeichnet wird (d. h. ob ihre Häufigkeit die Größe der Spalten oder Zeilen der Matrix erreicht).
   • Wenn ja, geben Sie den aktuellen Index zurück.

4. Ergebnis zurückgeben:

   • Der Index, bei dem entweder eine Zeile oder eine Spalte vollständig gezeichnet ist, ist unsere Antwort.

Detaillierte Schritte

1. Erstellen Sie eine Map position_map für jeden Wert in mat zu seiner (Zeilen-, Spalten-)Position.
2. Erstellen Sie die Arrays row_count und col_count, um die Anzahl der gezeichneten Zellen in jeder Zeile und Spalte zu verfolgen.
3. Durchlaufen Sie arr und aktualisieren Sie für jedes Element die jeweilige Zeilen- und Spaltenanzahl.
4. Wenn zu irgendeinem Zeitpunkt eine Zeile oder Spalte vollständig gezeichnet ist, geben Sie diesen Index zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2661. Erste vollständig bemalte Zeile oder Spalte

<?php /**
 * @param Integer[] $arr
 * @param Integer[][] $mat
 * @return Integer
 */
function firstCompleteIndex($arr, $mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2

$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>

Erläuterung:

1. Positionen vorbearbeiten:

   • Wir erstellen ein Wörterbuch position_map, in dem jeder Wert in mat seiner Position (Zeile, Spalte) zugeordnet wird. Dies hilft beim direkten Zugriff auf die Position eines beliebigen Werts in konstanter Zeit während der Durchquerung von arr.

2. Häufigkeit zählt:

   • Wir initialisieren die Arrays row_count und col_count mit Nullen. Diese Arrays verfolgen, wie oft eine Zelle in einer bestimmten Zeile oder Spalte gezeichnet wurde.

3. Durchlaufen des Arrays:

   • Für jeden Wert in arr suchen wir seine Position in position_map und erhöhen dann die entsprechenden Zeilen- und Spaltenanzahlen.
   • Nachdem wir die Zählungen aktualisiert haben, prüfen wir, ob eine Zeile oder Spalte ihre volle Größe erreicht hat (d. h. row_count[$row] == n oder col_count[$col] == m). Wenn ja, geben wir den aktuellen Index i zurück.

4. Ergebnis zurückgeben:

   • Der erste Index, bei dem entweder eine Zeile oder eine Spalte vollständig gezeichnet ist, wird zurückgegeben.

Zeitkomplexität:

• Vorverarbeitung: Wir erstellen position_map in O(m * n).
• Traversal: Wir verarbeiten jedes Element von arr (das eine Länge von m * n hat) und führen für jedes Element zeitkonstante Operationen durch, um die Zeilen- und Spaltenhäufigkeiten zu aktualisieren und zu überprüfen, was O( 1) Zeit.
• Insgesamt beträgt die Zeitkomplexität O(m * n).

Raumkomplexität:

• Wir speichern die Positionen aller Elemente in position_map und verwenden O(m n)-Raum für die Frequenzarrays. Daher beträgt die Raumkomplexität O(m * n).

Diese Lösung sollte das Problem innerhalb der gegebenen Einschränkungen effizient lösen.

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 vonErste vollständig bemalte Zeile oder Spalte. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!