The Celebrity Problem

Q: Wie hoch ist die Zeitkomplexität des Prominentenproblems?

Die Eliminierungslösungen laufen in O(n) -Zeit: n-1 Suchvorgänge finden den Kandidaten, und höchstens 2(n-1) überprüfen ihn. Die Zwei-Zeiger-Version benötigt O(1) zusätzlichen Speicherplatz und die Stack-Version O(n) . Jede Person anhand der Definition zu überprüfen, kostet O(n²) .

Q: Kann es mehr als einen Prominenten geben?

Nein. Wenn zwei Personen beide Berühmtheiten wären, wären sie allen bekannt, also würde jede die andere kennen. Eine Berühmtheit kennt jedoch niemanden, daher gibt es auf einer Party höchstens eine Berühmtheit.

Q: Wie hängt das Prominentenproblem mit Graphen zusammen?

Die Matrix ist die Adjazenzmatrix eines gerichteten Graphen: Eine Kante von i nach j bedeutet, dass i j kennt. Eine Berühmtheit ist ein Knoten mit Ausgangsgrad 0 und Eingangsgrad n-1 , also eine universelle Senke. Das Zählen der Grade liest die gesamte Matrix, während das Eliminationsverfahren die Senke findet, nachdem nur O(n) Zellen gelesen wurden.

MittelStack Zwei Zeiger Graphen

+10

Auf einer Party sind n Personen, nummeriert von 0 bis n-1. Du erhältst eine n × n-Matrix, in der matrix[i][j] 1 ist, wenn Person i Person j kennt, und 0, wenn nicht. Das Kennen ist einseitig: i kann j kennen, während j i nicht kennt.

Eine berühmte Person ist jemand, den alle anderen kennen und der niemanden kennt. Gib die Nummer dieser Person zurück oder -1, wenn es keine berühmte Person gibt.

Funktion

findCelebrity(matrix: integer-2d-array) → integer

matrixinteger-2d-array: Wer wen kennt: Zeile i, Spalte j ist 1, wenn Person i Person j kennt.
Gibt zurückinteger: die Nummer des Prominenten oder -1, falls es keinen gibt

Einschränkungen

2 ≤ n ≤ 150, wobei n die Anzahl der Zeilen und Spalten ist
matrix[i][j] ist 0 oder 1
matrix[i][i] = 0 für jede Person

Beispiele

Eingabe: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Ausgabe: 1
Erklärung: Zeile 1 besteht nur aus Nullen, also kennt Person 1 niemanden. In Spalte 1 steht in den Zeilen 0 und 2 jeweils eine 1, also kennen beide anderen Personen Person 1. Person 1 ist der Promi.

Weiterführende Frage

Angenommen, jeder Suchvorgang ist eine Frage, die du stellen musst. Wie wenige Fragen brauchst du im schlimmsten Fall, und kannst du unter 3(n-1) kommen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Person anhand der Definition zu überprüfen, erfordert etwa 2n² Abfragen. Eine Zelle matrix[a][b] schließt immer entweder a oder b aus, sodass nach n-1 Abfragen nur ein möglicher Kandidat übrig bleibt. Ein Durchlauf über die Zeile und Spalte des Kandidaten entscheidet dann, ob es sich um den Prominenten handelt.

Jede Person überprüfen

Idee

Person c ist die Berühmtheit, wenn Zeile c keine 1 enthält (sie kennt niemanden) und Spalte c in jeder Zeile außer der eigenen eine 1 enthält (alle kennen sie). Prüfe diese Definition der Reihe nach für jede Person und gib die erste zurück, auf die sie zutrifft.

Jede Person erfordert bis zu 2(n-1) Abfragen, insgesamt etwa 2n²: n = 150 bedeutet etwa 45.000 Abfragen.

Algorithmus

Für jede Person c von 0 bis n-1 betrachte jede andere Person other.
Wenn matrix[c][other] 1 ist oder matrix[other][c] 0 ist, ist c nicht die prominente Person: Gehe zur nächsten Person.
Wenn keine andere Person c ausschließt, gib c zurück.
Wenn alle Personen durchfallen, gib -1 zurück.

def findCelebrity(matrix):
    n = len(matrix)
    for c in range(n):
        is_celebrity = True
        for other in range(n):
            # c must know no one, and everyone else must know c.
            if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
                is_celebrity = False
                break
        if is_celebrity:
            return c
    return -1

Mit einem Stack eliminieren

Idee

Wenn matrix[a][b] 1 ist, kennt a jemanden und kann daher nicht die Berühmtheit sein. Wenn es 0 ist, kennt a b nicht, also kann b nicht die Berühmtheit sein. In beiden Fällen scheidet durch eine Abfrage eine Person endgültig aus. Setze alle auf einen Stapel, nimm zwei heraus, frage nach und lege die Person zurück, die noch infrage kommt: Nach n-1 Runden bleibt eine Person übrig.

Diese Person ist ein Kandidat, aber noch keine Antwort. Durch das Ausscheiden steht fest, dass niemand sonst die Berühmtheit sein kann, aber die Zeile und Spalte des Überlebenden werden nie überprüft. Im dritten Beispiel ist Person 2 der Überlebende; sie kennt Person 3, daher gibt die Prüfung -1 zurück. Die Prüfung kostet weitere 2(n-1) Abfragen, insgesamt also O(n).

Algorithmus

Lege jede Person auf einen Stapel.
Solange der Stapel mehr als eine Person enthält, nimm a und b vom Stapel.
Wenn a b kennt, lege b zurück auf den Stapel; andernfalls lege a zurück.
Nimm die letzte Person als Kandidaten. Wenn sie irgendjemanden kennt oder irgendjemand sie nicht kennt, gib -1 zurück.
Andernfalls gib den Kandidaten zurück.

def findCelebrity(matrix):
    n = len(matrix)
    candidates = list(range(n))
    # Each question removes one person who cannot be the celebrity.
    while len(candidates) > 1:
        a = candidates.pop()
        b = candidates.pop()
        candidates.append(b if matrix[a][b] == 1 else a)
    c = candidates[0]
    # The survivor is only a candidate: check every other person.
    for other in range(n):
        if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
            return -1
    return c

Zwei Zeiger, dann überprüfen

Idee

Der Stapel enthält nur Personen, die noch nicht ausgeschlossen wurden, und ihre Reihenfolge spielt keine Rolle. Ersetze ihn durch zwei Zeiger: a auf die erste Person und b auf die letzte. Alle außerhalb des Bereichs von a bis b sind bereits ausgeschieden. Wenn a b kennt, scheidet a aus; andernfalls scheidet b aus. Wenn sich die Zeiger treffen, ist die Person unter ihnen die Kandidatin.

Im ersten Beispiel ist matrix[0][2] 0, also scheidet Person 2 aus; dann ist matrix[0][1] 1, also scheidet Person 0 aus. Die Zeiger treffen sich bei Person 1, die die Prüfung besteht. Das sind n-1 Zugriffe plus höchstens 2(n-1), bei zwei Ganzzahlen zusätzlichem Speicherbedarf.

Algorithmus

Setze a = 0 und b = n-1.
Solange a < b gilt: Wenn matrix[a][b] 1 ist, addiere 1 zu a; andernfalls subtrahiere 1 von b.
Der Kandidat ist a. Überprüfe für jede andere Person, dass der Kandidat sie nicht kennt und dass sie den Kandidaten kennt.
Gib den Kandidaten zurück, wenn alle Überprüfungen zutreffen, andernfalls -1.

def findCelebrity(matrix):
    n = len(matrix)
    a, b = 0, n - 1
    # Each question rules out one of the two people.
    while a < b:
        if matrix[a][b] == 1:
            a += 1  # a knows someone, so a is not the celebrity
        else:
            b -= 1  # a does not know b, so b is not the celebrity
    # a is the only person left who could be the celebrity: check it.
    for other in range(n):
        if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
            return -1
    return a

Stolperfallen und Grenzfälle

Den Überlebenden zurückgeben, ohne ihn zu überprüfen. In [[0, 1], [1, 0]] ist der Überlebende eine von zwei Personen, die einander kennen, und die Antwort ist -1.
Nur eine Seite überprüfen. Das dritte Beispiel scheitert nur an der Zeile: Alle kennen Person 2, aber Person 2 kennt Person 3.
Die Diagonale mitzählen. matrix[c][c] ist 0, daher weist eine Spaltenprüfung, bei der other == c nicht übersprungen wird, jede echte Berühmtheit zurück.
Die Zelle verkehrt herum lesen. matrix[a][b] = 1 schließt a aus, nicht b. Wenn du die Rollen vertauschst, wirfst du die echte Berühmtheit weg.
In Lua oder R einen 1-basierten Index zurückgeben. Die Personen sind ab 0 nummeriert, ziehe also 1 ab, bevor du den Wert zurückgibst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Prominentenproblems?

Die Eliminierungslösungen laufen in O(n)-Zeit: n-1 Suchvorgänge finden den Kandidaten, und höchstens 2(n-1) überprüfen ihn. Die Zwei-Zeiger-Version benötigt O(1) zusätzlichen Speicherplatz und die Stack-Version O(n). Jede Person anhand der Definition zu überprüfen, kostet O(n²).

Kann es mehr als einen Prominenten geben?

Nein. Wenn zwei Personen beide Berühmtheiten wären, wären sie allen bekannt, also würde jede die andere kennen. Eine Berühmtheit kennt jedoch niemanden, daher gibt es auf einer Party höchstens eine Berühmtheit.

Wie hängt das Prominentenproblem mit Graphen zusammen?

Die Matrix ist die Adjazenzmatrix eines gerichteten Graphen: Eine Kante von i nach j bedeutet, dass i j kennt. Eine Berühmtheit ist ein Knoten mit Ausgangsgrad 0 und Eingangsgrad n-1, also eine universelle Senke. Das Zählen der Grade liest die gesamte Matrix, während das Eliminationsverfahren die Senke findet, nachdem nur O(n) Zellen gelesen wurden.

def findCelebrity(matrix):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]

Erwartete Ausgabe

The Celebrity Problem

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jede Person überprüfen

Mit einem Stack eliminieren

Zwei Zeiger, dann überprüfen

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben