The Celebrity Problem

Q: ¿Cuál es la complejidad temporal del problema de la celebridad?

Las soluciones de eliminación se ejecutan en tiempo O(n) : n-1 búsquedas encuentran al candidato y, como máximo, 2(n-1) lo comprueban. La versión de dos punteros usa espacio adicional O(1) y la versión con pila, O(n) . Comprobar a cada persona según la definición cuesta O(n²) .

Q: ¿Puede haber más de una celebridad?

No. Si dos personas fueran celebridades, ambas serían conocidas por todos, así que cada una conocería a la otra. Pero una celebridad no conoce a nadie, por lo que en una fiesta puede haber como máximo una celebridad.

Q: ¿Qué relación tiene el problema de la celebridad con los grafos?

La matriz es la matriz de adyacencia de un grafo dirigido: una arista de i a j significa que i conoce a j . Una celebridad es un nodo con grado de salida 0 y grado de entrada n-1 , un sumidero universal. Contar los grados requiere leer toda la matriz, mientras que la eliminación encuentra el sumidero después de leer solo O(n) celdas.

MedioPila Dos punteros Grafos

+10

Hay n personas en una fiesta, numeradas del 0 al n-1. Recibes una matriz n × n donde matrix[i][j] es 1 si la persona i conoce a la persona j y 0 si no. Conocerse es unidireccional: i puede conocer a j mientras que j no conoce a i.

Una celebridad es una persona a quien conocen todas las demás y que no conoce a nadie. Devuelve el número de la celebridad o -1 si no hay ninguna.

Función

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

matrixinteger-2d-array: quién conoce a quién: la fila i, la columna j es 1 si la persona i conoce a la persona j
Devuelveinteger: el número de la celebridad, o -1 si no hay ninguna

Restricciones

2 ≤ n ≤ 150, donde n es el número de filas y de columnas
matrix[i][j] es 0 o 1
matrix[i][i] = 0 para cada persona

Ejemplos

Entrada: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Salida: 1
Explicación: La fila 1 contiene solo ceros, así que la persona 1 no conoce a nadie. La columna 1 tiene un 1 en las filas 0 y 2, así que las otras dos personas conocen a la persona 1. La persona 1 es la celebridad.

Para ir más allá

Supón que cada búsqueda es una pregunta que debes hacer. ¿Cuál es el menor número de preguntas que necesitas en el peor de los casos, y puedes bajar de 3(n-1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Comprobar a cada persona según la definición requiere unas 2n² consultas. Una celda matrix[a][b] siempre descarta a a o a b, así que n-1 consultas dejan un único candidato. Después, un recorrido por la fila y la columna del candidato determina si es la celebridad.

Comprueba a cada persona

Intuición

La persona c es la celebridad cuando la fila c no contiene ningún 1 (no conoce a nadie) y la columna c contiene un 1 en todas las filas excepto en la suya (todo el mundo la conoce). Comprueba esa definición para cada persona por turno y devuelve a la primera que la cumpla.

Cada persona requiere hasta 2(n-1) consultas, unas 2n² en total: n = 150 significa unas 45,000 consultas.

Algoritmo

Para cada persona c, desde 0 hasta n-1, mira a todas las demás personas other.
Si matrix[c][other] es 1, o matrix[other][c] es 0, c no es la celebridad: pasa a la siguiente persona.
Si ninguna otra persona descarta a c, devuelve c.
Si todas las personas fallan, devuelve -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

Eliminar con una pila

Intuición

Si matrix[a][b] es 1, a conoce a alguien y no puede ser la celebridad. Si es 0, a no conoce a b, así que b no puede ser la celebridad. En cualquier caso, una consulta elimina definitivamente a una persona. Pon a todos en una pila, saca a dos, pregunta y vuelve a poner a quien todavía pueda serlo: después de n-1 rondas queda una persona.

Esa persona es una candidata, no una respuesta. La eliminación demuestra que nadie más puede ser la celebridad, pero nunca comprueba la fila ni la columna de la persona restante. En el tercer ejemplo, la persona restante es la persona 2, que conoce a la persona 3, así que la comprobación devuelve -1. La comprobación cuesta 2(n-1) consultas más, O(n) en total.

Algoritmo

Apila a todas las personas.
Mientras la pila contenga a más de una persona, extrae a y b.
Si a conoce a b, vuelve a apilar b; de lo contrario, vuelve a apilar a.
Toma a la última persona como candidata. Si conoce a alguien o alguien no la conoce, devuelve -1.
De lo contrario, devuelve a 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

Dos punteros, después verifica

Intuición

La pila solo contiene a las personas que aún no se han descartado, y su orden no importa. Reemplázala por dos punteros, a en la primera persona y b en la última: todos los que están fuera del intervalo de a a b ya han sido descartados. Si a conoce a b, se descarta a a; de lo contrario, se descarta a b. Cuando los punteros se encuentran, la persona señalada por ellos es la candidata.

En el primer ejemplo, matrix[0][2] es 0, así que se descarta a la persona 2; después, matrix[0][1] es 1, así que se descarta a la persona 0. Los punteros se encuentran en la persona 1, que pasa la comprobación. Eso supone n-1 consultas más, como máximo, 2(n-1), con dos enteros de memoria adicional.

Algoritmo

Establece a = 0 y b = n-1.
Mientras a < b: si matrix[a][b] es 1, suma 1 a a; de lo contrario, resta 1 a b.
El candidato es a. Para cada una de las demás personas, comprueba que el candidato no las conoce y que ellas conocen al candidato.
Devuelve el candidato si se cumplen todas las comprobaciones; de lo contrario, devuelve -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

Errores comunes y casos límite

Devolver al superviviente sin comprobarlo. En [[0, 1], [1, 0]], el superviviente es una de las dos personas que se conocen, y la respuesta es -1.
Comprobar solo un lado. El tercer ejemplo falla solo en la fila: todos conocen a la persona 2, pero la persona 2 conoce a la persona 3.
Contar la diagonal. matrix[c][c] es 0, así que una comprobación de columna que no omita other == c rechaza a todas las celebridades reales.
Leer la celda al revés. matrix[a][b] = 1 descarta a a, no a b. Intercambiar los roles descarta a la celebridad real.
Devolver un índice basado en 1 en Lua o R. Las personas se numeran desde 0, así que resta 1 antes de devolver el resultado.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del problema de la celebridad?

Las soluciones de eliminación se ejecutan en tiempo O(n): n-1 búsquedas encuentran al candidato y, como máximo, 2(n-1) lo comprueban. La versión de dos punteros usa espacio adicional O(1) y la versión con pila, O(n). Comprobar a cada persona según la definición cuesta O(n²).

¿Puede haber más de una celebridad?

No. Si dos personas fueran celebridades, ambas serían conocidas por todos, así que cada una conocería a la otra. Pero una celebridad no conoce a nadie, por lo que en una fiesta puede haber como máximo una celebridad.

¿Qué relación tiene el problema de la celebridad con los grafos?

La matriz es la matriz de adyacencia de un grafo dirigido: una arista de i a j significa que i conoce a j. Una celebridad es un nodo con grado de salida 0 y grado de entrada n-1, un sumidero universal. Contar los grados requiere leer toda la matriz, mientras que la eliminación encuentra el sumidero después de leer solo O(n) celdas.

def findCelebrity(matrix):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

The Celebrity Problem

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba a cada persona

Eliminar con una pila

Dos punteros, después verifica

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares