The Celebrity Problem

Q: Jaka jest złożoność czasowa problemu celebryty?

Rozwiązania oparte na eliminacji działają w czasie O(n) : n-1 wyszukiwań znajduje kandydata, a co najwyżej 2(n-1) sprawdzeń go weryfikuje. Wersja z dwoma wskaźnikami wykorzystuje dodatkowe miejsce O(1) , a wersja ze stosem O(n) . Sprawdzenie każdej osoby zgodnie z definicją kosztuje O(n²) .

Q: Czy może być więcej niż jedna celebrytka lub jeden celebryta?

Nie. Gdyby dwie osoby były celebrytami, każda byłaby znana wszystkim, więc każda znałaby tę drugą. Celebryta nie zna jednak nikogo, więc na przyjęciu może być co najwyżej jeden celebryta.

Q: Jaki związek ma problem celebryty z grafami?

Macierz jest macierzą sąsiedztwa grafu skierowanego: krawędź z i do j oznacza, że i zna j . Celebryta to wierzchołek o stopniu wyjściowym 0 i stopniu wejściowym n-1 , czyli uniwersalny ujście. Liczenie stopni wymaga odczytania całej macierzy, podczas gdy eliminacja pozwala znaleźć ujście po odczytaniu tylko O(n) komórek.

ŚrednieStos Dwa wskaźniki Grafy

+10

Na przyjęciu jest n osób ponumerowanych od 0 do n-1. Otrzymujesz macierz n × n, w której matrix[i][j] ma wartość 1, jeśli osoba i zna osobę j, a 0, jeśli jej nie zna. Znajomość jest jednostronna: i może znać j, podczas gdy j nie zna i.

Gwiazda to osoba, którą zna każda inna osoba i która nie zna nikogo. Zwróć numer gwiazdy lub -1, jeśli nie ma gwiazdy.

Funkcja

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

matrixinteger-2d-array: kto kogo zna: wiersz i, kolumna j ma wartość 1, jeśli osoba i zna osobę j
Zwracainteger: numer celebryty lub -1, jeśli go nie ma

Ograniczenia

2 ≤ n ≤ 150, gdzie n oznacza liczbę wierszy i kolumn
matrix[i][j] ma wartość 0 lub 1
matrix[i][i] = 0 dla każdej osoby

Przykłady

Wejście: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Wyjście: 1
Wyjaśnienie: Wiersz 1 zawiera same zera, więc osoba 1 nikogo nie zna. W kolumnie 1 wiersze 0 i 2 zawierają 1, więc obie pozostałe osoby znają osobę 1. Osoba 1 jest celebrytą.

Pytanie dodatkowe

Załóżmy, że każde wyszukiwanie to pytanie, które musisz zadać. Jak najmniej pytań potrzebujesz w najgorszym przypadku i czy możesz zejść poniżej 3(n-1)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Sprawdzenie każdej osoby pod kątem spełniania definicji wymaga około 2n² wyszukiwań. Jedna komórka matrix[a][b] zawsze wyklucza jedną z osób a i b, więc n-1 wyszukiwań pozostawia jednego kandydata. Jedno przejście po wierszu i kolumnie kandydata rozstrzyga, czy jest celebrytą.

Sprawdź każdą osobę

Intuicja

Osoba c jest celebrytą, gdy wiersz c nie zawiera żadnej jedynki (nie zna nikogo), a kolumna c zawiera jedynkę w każdym wierszu poza własnym (wszyscy ją znają). Sprawdź tę definicję kolejno dla każdej osoby i zwróć pierwszą, która ją spełnia.

Każda osoba wymaga maksymalnie 2(n-1) odczytów, czyli łącznie około 2n²: dla n = 150 oznacza to około 45 000 odczytów.

Algorytm

Dla każdej osoby c od 0 do n-1 sprawdź każdą inną osobę other.
Jeśli matrix[c][other] wynosi 1 lub matrix[other][c] wynosi 0, c nie jest celebrytą: przejdź do następnej osoby.
Jeśli żadna inna osoba nie wyklucza c, zwróć c.
Jeśli każda osoba nie spełnia warunku, zwróć -1.

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

Eliminacja za pomocą stosu

Intuicja

Jeśli matrix[a][b] ma wartość 1, a kogoś zna i nie może być celebrytą. Jeśli ma wartość 0, a nie zna b, więc b nie może być celebrytą. W obu przypadkach jedno sprawdzenie na dobre eliminuje jedną osobę. Umieść wszystkie osoby na stosie, zdejmij dwie, zadaj pytanie i odłóż z powrotem tę, która nadal może być celebrytą: po n-1 rundach zostanie jedna osoba.

Ta osoba jest kandydatem, a nie odpowiedzią. Eliminacja pokazuje, że nikt inny nie może być celebrytą, ale nie sprawdza wiersza ani kolumny ocalałej osoby. W trzecim przykładzie ocalałą osobą jest osoba 2, która zna osobę 3, więc sprawdzenie zwraca -1. Sprawdzenie wymaga jeszcze 2(n-1) zapytań, czyli łącznie O(n).

Algorytm

Umieść każdą osobę na stosie.
Gdy na stosie znajduje się więcej niż jedna osoba, zdejmij a i b.
Jeśli a zna b, odłóż b z powrotem na stos; w przeciwnym razie odłóż z powrotem a.
Przyjmij ostatnią osobę za kandydata. Jeśli zna ona kogokolwiek lub ktokolwiek jej nie zna, zwróć -1.
W przeciwnym razie zwróć kandydata.

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

Dwa wskaźniki, a następnie weryfikacja

Intuicja

Stos przechowuje tylko osoby, których jeszcze nie wykluczono, a ich kolejność nie ma znaczenia. Zastąp go dwoma wskaźnikami: a wskazującym pierwszą osobę i b wskazującym ostatnią. Każda osoba poza zakresem od a do b jest już wykluczona. Jeśli a zna b, wykluczona zostaje osoba a; w przeciwnym razie wykluczona zostaje osoba b. Gdy wskaźniki się spotkają, osoba, na którą wskazują, jest kandydatem.

W pierwszym przykładzie matrix[0][2] ma wartość 0, więc osoba 2 zostaje wykluczona; następnie matrix[0][1] ma wartość 1, więc osoba 0 zostaje wykluczona. Wskaźniki spotykają się przy osobie 1, która przechodzi sprawdzenie. To n-1 odczytów oraz najwyżej 2(n-1) dodatkowych, przy użyciu dwóch liczb całkowitych pamięci.

Algorytm

Ustaw a = 0 i b = n-1.
Gdy a < b: jeśli matrix[a][b] wynosi 1, zwiększ a o 1; w przeciwnym razie zmniejsz b o 1.
Kandydatem jest a. Dla każdej innej osoby sprawdź, czy kandydat jej nie zna i czy ona zna kandydata.
Zwróć kandydata, jeśli wszystkie warunki są spełnione; w przeciwnym razie zwróć -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

Pułapki i przypadki brzegowe

Zwrócenie ocalałej osoby bez sprawdzenia jej. W [[0, 1], [1, 0]] ocalała osoba to jedna z dwóch osób, które się znają, więc odpowiedzią jest -1.
Sprawdzenie tylko jednej strony. W trzecim przykładzie warunek nie jest spełniony tylko w wierszu: wszyscy znają osobę 2, ale osoba 2 zna osobę 3.
Uwzględnienie przekątnej. matrix[c][c] ma wartość 0, więc sprawdzenie kolumny, które nie pomija other == c, odrzuca każdą prawdziwą gwiazdę.
Odczytanie komórki w odwrotnym kierunku. matrix[a][b] = 1 wyklucza a, a nie b. Zamiana ról powoduje odrzucenie prawdziwej gwiazdy.
Zwrócenie indeksu liczonego od 1 w Lua lub R. Osoby są numerowane od 0, więc odejmij 1 przed zwróceniem wyniku.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu celebryty?

Rozwiązania oparte na eliminacji działają w czasie O(n): n-1 wyszukiwań znajduje kandydata, a co najwyżej 2(n-1) sprawdzeń go weryfikuje. Wersja z dwoma wskaźnikami wykorzystuje dodatkowe miejsce O(1), a wersja ze stosem O(n). Sprawdzenie każdej osoby zgodnie z definicją kosztuje O(n²).

Czy może być więcej niż jedna celebrytka lub jeden celebryta?

Nie. Gdyby dwie osoby były celebrytami, każda byłaby znana wszystkim, więc każda znałaby tę drugą. Celebryta nie zna jednak nikogo, więc na przyjęciu może być co najwyżej jeden celebryta.

Jaki związek ma problem celebryty z grafami?

Macierz jest macierzą sąsiedztwa grafu skierowanego: krawędź z i do j oznacza, że i zna j. Celebryta to wierzchołek o stopniu wyjściowym 0 i stopniu wejściowym n-1, czyli uniwersalny ujście. Liczenie stopni wymaga odczytania całej macierzy, podczas gdy eliminacja pozwala znaleźć ujście po odczytaniu tylko O(n) komórek.

def findCelebrity(matrix):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

The Celebrity Problem

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdą osobę

Eliminacja za pomocą stosu

Dwa wskaźniki, a następnie weryfikacja

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania