The Celebrity Problem

Q: Qual è la complessità temporale del problema delle celebrità?

Le soluzioni basate sull’eliminazione hanno una complessità temporale di O(n) : n-1 ricerche individuano il candidato e al massimo 2(n-1) lo verificano. La versione con due puntatori usa uno spazio aggiuntivo di O(1) , mentre la versione con stack usa O(n) . Verificare ogni persona rispetto alla definizione costa O(n²) .

Q: Può esserci più di una celebrità?

No. Se due persone fossero entrambe celebrità, ognuna sarebbe conosciuta da tutti, quindi ognuna conoscerebbe l’altra. Ma una celebrità non conosce nessuno, quindi a una festa ci può essere al massimo una celebrità.

Q: In che modo il problema delle celebrità è legato ai grafi?

La matrice è la matrice di adiacenza di un grafo orientato: un arco da i a j significa che i conosce j . Una celebrità è un nodo con grado uscente 0 e grado entrante n-1 , un pozzo universale. Contare i gradi richiede di leggere l’intera matrice, mentre l’eliminazione trova il pozzo dopo aver letto solo O(n) celle.

MedioStack Due puntatori Grafi

+10

A una festa ci sono n persone, numerate da 0 a n-1. Ti viene fornita una matrice n × n in cui matrix[i][j] è 1 se la persona i conosce la persona j e 0 in caso contrario. La conoscenza è a senso unico: i può conoscere j mentre j non conosce i.

Una celebrità è una persona che tutti gli altri conoscono e che non conosce nessuno. Restituisci il numero della celebrità, oppure -1 se non c'è alcuna celebrità.

Funzione

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

matrixinteger-2d-array: chi conosce chi: la riga i, la colonna j è 1 se la persona i conosce la persona j
Restituisceinteger: il numero della celebrità, oppure -1 se non ce n'è nessuna

Vincoli

2 ≤ n ≤ 150, dove n è il numero di righe e di colonne
matrix[i][j] è 0 oppure 1
matrix[i][i] = 0 per ogni persona

Esempi

Input: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Output: 1
Spiegazione: La riga 1 contiene solo zeri, quindi la persona 1 non conosce nessuno. La colonna 1 contiene un 1 nelle righe 0 e 2, quindi entrambe le altre persone conoscono la persona 1. La persona 1 è la celebrità.

Per approfondire

Supponi che ogni ricerca sia una domanda da fare. Qual è il numero minimo di domande necessarie nel caso peggiore e puoi scendere sotto 3(n-1)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Verificare ogni persona rispetto alla definizione richiede circa 2n² ricerche. Una cella matrix[a][b] esclude sempre uno tra a e b, quindi n-1 ricerche lasciano un unico candidato. Un passaggio sulla riga e sulla colonna del candidato stabilisce poi se è la celebrità.

Controlla ogni persona

Intuizione

La persona c è la celebrità quando la riga c non contiene alcun 1 (non conosce nessuno) e la colonna c contiene un 1 in tutte le righe tranne la propria (tutti la conoscono). Verifica questa definizione per ogni persona, una alla volta, e restituisci la prima che la soddisfa.

Per ogni persona servono fino a 2(n-1) consultazioni, circa 2n² in totale: n = 150 significa circa 45.000 consultazioni.

Algoritmo

Per ogni persona c da 0 a n-1, esamina ogni altra persona other.
Se matrix[c][other] è 1, oppure matrix[other][c] è 0, c non è la celebrità: passa alla persona successiva.
Se nessun'altra persona esclude c, restituisci c.
Se tutte le persone non superano il controllo, restituisci -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

Elimina con uno stack

Intuizione

Se matrix[a][b] è 1, a conosce qualcuno e non può essere la celebrità. Se è 0, a non conosce b, quindi b non può essere la celebrità. In entrambi i casi, una sola consultazione elimina definitivamente una persona. Metti tutti su una pila, estrai due persone, fai la domanda e rimetti sulla pila quella che può ancora esserlo: dopo n-1 turni rimane una persona.

Quella persona è una candidata, non una risposta. L’eliminazione mostra che nessun altro può essere la celebrità, ma non controlla mai la riga e la colonna della persona rimasta. Nel terzo esempio la persona rimasta è la persona 2, che conosce la persona 3, quindi il controllo restituisce -1. Il controllo richiede altre 2(n-1) consultazioni, per un totale di O(n).

Algoritmo

Inserisci ogni persona in uno stack.
Mentre lo stack contiene più di una persona, estrai a e b.
Se a conosce b, reinserisci b; altrimenti reinserisci a.
Prendi l'ultima persona come candidata. Se conosce qualcuno o qualcuno non la conosce, restituisci -1.
Altrimenti restituisci la candidata.

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

Due puntatori, poi verifica

Intuizione

La pila contiene solo le persone che non sono ancora state escluse, e il loro ordine non è importante. Sostituiscila con due puntatori, a sulla prima persona e b sull’ultima: tutti quelli fuori dall’intervallo da a a b sono già esclusi. Se a conosce b, a è escluso; altrimenti è escluso b. Quando i puntatori si incontrano, la persona indicata è la candidata.

Nel primo esempio, matrix[0][2] è 0, quindi la persona 2 è esclusa; poi matrix[0][1] è 1, quindi la persona 0 è esclusa. I puntatori si incontrano sulla persona 1, che supera la verifica. Sono n-1 consultazioni più al massimo 2(n-1), con due interi di memoria aggiuntiva.

Algoritmo

Imposta a = 0 e b = n-1.
Mentre a < b: se matrix[a][b] è 1, aggiungi 1 a a; altrimenti sottrai 1 da b.
Il candidato è a. Per ogni altra persona, verifica che il candidato non la conosca e che lei conosca il candidato.
Restituisci il candidato se tutte le verifiche sono soddisfatte, altrimenti -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

Trappole e casi limite

Restituire il sopravvissuto senza verificarlo. In [[0, 1], [1, 0]] il sopravvissuto è una delle due persone che si conoscono, quindi la risposta è -1.
Controllare solo un lato. Il terzo esempio non supera solo il controllo della riga: tutti conoscono la persona 2, ma la persona 2 conosce la persona 3.
Contare la diagonale. matrix[c][c] è 0, quindi un controllo della colonna che non salta other == c esclude ogni vera celebrità.
Leggere la cella al contrario. matrix[a][b] = 1 esclude a, non b. Scambiare i ruoli elimina la vera celebrità.
Restituire un indice a partire da 1 in Lua o R. Le persone sono numerate a partire da 0, quindi sottrai 1 prima di restituire il valore.

Domande frequenti3

Qual è la complessità temporale del problema delle celebrità?

Le soluzioni basate sull’eliminazione hanno una complessità temporale di O(n): n-1 ricerche individuano il candidato e al massimo 2(n-1) lo verificano. La versione con due puntatori usa uno spazio aggiuntivo di O(1), mentre la versione con stack usa O(n). Verificare ogni persona rispetto alla definizione costa O(n²).

Può esserci più di una celebrità?

No. Se due persone fossero entrambe celebrità, ognuna sarebbe conosciuta da tutti, quindi ognuna conoscerebbe l’altra. Ma una celebrità non conosce nessuno, quindi a una festa ci può essere al massimo una celebrità.

In che modo il problema delle celebrità è legato ai grafi?

La matrice è la matrice di adiacenza di un grafo orientato: un arco da i a j significa che i conosce j. Una celebrità è un nodo con grado uscente 0 e grado entrante n-1, un pozzo universale. Contare i gradi richiede di leggere l’intera matrice, mentre l’eliminazione trova il pozzo dopo aver letto solo O(n) celle.

def findCelebrity(matrix):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

The Celebrity Problem

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni persona

Elimina con uno stack

Due puntatori, poi verifica

Trappole e casi limite

Domande frequenti3

Problemi simili