Java / C # - Array [] [] Komplexitätsaufgabe [doppelt]

Question

Java / C # - Array [] [] Komplexitätsaufgabe [doppelt]

8

Ich beschäftige mich mit einer problematischen Komplexitätsfrage über meine Universität:

Programmeingabe: A n x n Array[][] , die entweder mit 0 oder 1 gefüllt ist.

DEFINITION: Definieren Sie k als SINK , wenn in der Zeile k alle Werte 0 sind und in der Spalte k alle Werte 1 (außer [k][k] selbst muss 0 ) sein

Programmausgabe: Gibt es eine k-Zahl, die ein SINK ist? Wenn ja, geben Sie k zurück, sonst geben Sie -1 zurück.

Beispiel:

An Arr A k = 3 ist ein SINK, in Arr B gibt es kein SINK, also wird -1 zurückgegeben.

Das Hauptproblem bei dieser Aufgabe ist, dass die Komplexität des Programms unter O(n^2) liegen muss. Ich habe es geschafft, dies mit dieser Komplexität zu lösen, indem ich über die schräge Linie die Zeilen und Spalten summiere. Ich habe keinen Weg gefunden, dies mit O(logn) oder O(n) zu lösen. Außerdem verhindert die Aufgabe die Verwendung eines anderen Arrays [] (aufgrund der Speicherkomplexität). Kann irgendjemand Licht in diese Sache fallen lassen? Danke im Voraus!

algorithm java arrays c# task

Oran Ge 29.11.2013, 10:06

quelle

1 Antwort

Tags und Links algorithm java arrays c# task

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Berechnung Block / Gesicht Kamera / Cursor hat Fokus auf 3D-Block Welt

score 4 · Accepted Answer

Um die Antwort, auf die sich harold in den OP-Kommentaren bezieht, explizit zu machen: Beginnen Sie mit einer Liste aller n -Indizes, S = {0, 1, .., n-1} . Dies sind unsere Kandidaten für Senken. Bei jedem Schritt eliminieren wir einen von ihnen.

Betrachten Sie die ersten beiden Elemente von S , sagen wir i und j .
Überprüfen Sie, ob A[i, j] 1 ist.
- Wenn ja, entferne i von S (weil die i Zeile nicht alle 0s ist, also kann i nicht unsere Senke sein)
- Wenn nicht, entferne j von S (weil die j Spalte nicht alle 1s ist, also kann j nicht unsere Senke sein)
Wenn noch zwei oder mehr Elemente in S vorhanden sind, gehen Sie zurück zu Schritt 1.
Wenn wir zum letzten Element kommen, sagen wir k , überprüfen Sie, ob die k .te Zeile null ist und die k Spalte (außer A[k,k] ) ) sind alle Einsen.
- Wenn dies der Fall ist, ist k eine Senke und Sie können sie zurückgeben.
- Wenn dies nicht der Fall ist, hat die Matrix keine Senke und Sie können -1 zurückgeben.

Es gibt n elements in S , um mit zu beginnen, jeder Schritt eliminiert einen von ihnen und jeder Schritt benötigt konstante Zeit, also ist es O (n) insgesamt.

Sie erwähnen, dass Sie kein zweites Array verwenden möchten. Wenn das wirklich streng ist, können Sie stattdessen nur zwei ganze Zahlen verwenden, eine, die den "Überlebenden" aus dem letzten Schritt darstellt, und eine, die angibt, wie weit Sie in die Sequenz 0, 1, .., n-1 gehen sind.

Ich habe diesen Algorithmus noch nie zuvor gesehen und ich bin ziemlich beeindruckt von seiner Einfachheit. Prost.