The Celebrity Problem

Q: Qual é a complexidade de tempo do problema da celebridade?

As soluções por eliminação têm complexidade de tempo O(n) : n-1 consultas encontram o candidato e no máximo 2(n-1) o verificam. A versão com dois ponteiros usa espaço extra O(1) , e a versão com pilha, O(n) . Verificar cada pessoa em relação à definição custa O(n²) .

Q: Pode haver mais de uma celebridade?

Não. Se duas pessoas fossem celebridades, cada uma seria conhecida por todos, então cada uma conheceria a outra. Mas uma celebridade não conhece ninguém, então uma festa tem no máximo uma celebridade.

Q: Como o problema das celebridades está relacionado a grafos?

A matriz é a matriz de adjacência de um grafo direcionado: uma aresta de i para j significa que i conhece j . Uma celebridade é um nó com grau de saída 0 e grau de entrada n-1 , um sorvedouro universal. Contar os graus exige ler a matriz inteira, enquanto a eliminação encontra o sorvedouro após ler apenas O(n) células.

MédioPilha Dois ponteiros Grafos

+10

Há n pessoas em uma festa, numeradas de 0 a n-1. Você recebe uma matriz n × n em que matrix[i][j] é 1 se a pessoa i conhece a pessoa j e 0 caso contrário. Conhecer alguém é uma via de mão única: i pode conhecer j sem que j conheça i.

Uma celebridade é uma pessoa que todas as outras pessoas conhecem e que não conhece ninguém. Retorne o número da celebridade ou -1 se não houver nenhuma celebridade.

Função

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

matrixinteger-2d-array: quem conhece quem: a linha i, coluna j é 1 se a pessoa i conhece a pessoa j
Retornainteger: o número da celebridade, ou -1 se não houver nenhuma

Restrições

2 ≤ n ≤ 150, em que n é o número de linhas e de colunas
matrix[i][j] é 0 ou 1
matrix[i][i] = 0 para cada pessoa

Exemplos

Entrada: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Saída: 1
Explicação: A linha 1 contém apenas zeros, então a pessoa 1 não conhece ninguém. A coluna 1 contém um 1 nas linhas 0 e 2, então ambas as outras pessoas conhecem a pessoa 1. A pessoa 1 é a celebridade.

Para ir além

Suponha que cada busca seja uma pergunta que você precisa fazer. Qual é o menor número de perguntas de que você precisa no pior caso, e é possível ficar abaixo de 3(n-1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Testar cada pessoa em relação à definição leva cerca de 2n² consultas. Uma célula matrix[a][b] sempre elimina uma das pessoas, a ou b, então n-1 consultas deixam um único candidato. Uma verificação da linha e da coluna do candidato então determina se ele é a celebridade.

Verifique cada pessoa

Intuição

A pessoa c é a celebridade quando a linha c não contém nenhum 1 (ela não conhece ninguém) e a coluna c contém um 1 em todas as linhas, exceto na dela (todos a conhecem). Teste essa definição para cada pessoa, uma de cada vez, e retorne a primeira que passar.

Cada pessoa exige até 2(n-1) consultas, cerca de 2n² no total: n = 150 significa cerca de 45.000 consultas.

Algoritmo

Para cada pessoa c, de 0 a n-1, observe todas as outras pessoas other.
Se matrix[c][other] for 1 ou matrix[other][c] for 0, c não é a celebridade: passe para a próxima pessoa.
Se nenhuma outra pessoa descartar c, retorne c.
Se todas as pessoas falharem, retorne -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

Elimine com uma pilha

Intuição

Se matrix[a][b] for 1, a conhece alguém e não pode ser a celebridade. Se for 0, a não conhece b, então b não pode ser a celebridade. De qualquer forma, uma consulta elimina uma pessoa de vez. Coloque todos em uma pilha, retire dois, pergunte e coloque de volta quem ainda pode ser a celebridade: após n-1 rodadas, resta uma pessoa.

Essa pessoa é uma candidata, não uma resposta. A eliminação mostra que ninguém mais pode ser a celebridade, mas nunca verifica a linha e a coluna da sobrevivente. No terceiro exemplo, a sobrevivente é a pessoa 2, que conhece a pessoa 3, então a verificação retorna -1. A verificação custa mais 2(n-1) consultas, totalizando O(n).

Algoritmo

Empilhe todas as pessoas.
Enquanto a pilha tiver mais de uma pessoa, desempilhe a e b.
Se a conhece b, coloque b de volta na pilha; caso contrário, coloque a de volta na pilha.
Considere a última pessoa como candidata. Se ela conhece alguém, ou se alguém não a conhece, retorne -1.
Caso contrário, retorne a 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

Dois ponteiros, depois verifique

Intuição

A pilha contém apenas as pessoas que ainda não foram descartadas, e a ordem delas não importa. Substitua-a por dois ponteiros, a na primeira pessoa e b na última: todos que estão fora do intervalo de a a b já foram descartados. Se a conhece b, a é descartado; caso contrário, b é descartado. Quando os ponteiros se encontram, a pessoa sob eles é a candidata.

No primeiro exemplo, matrix[0][2] é 0, então a pessoa 2 é descartada; depois, matrix[0][1] é 1, então a pessoa 0 é descartada. Os ponteiros se encontram na pessoa 1, que passa na verificação. São n-1 consultas, mais no máximo 2(n-1), com dois inteiros de memória extra.

Algoritmo

Defina a = 0 e b = n-1.
Enquanto a < b: se matrix[a][b] for 1, some 1 a a; caso contrário, subtraia 1 de b.
O candidato é a. Para cada outra pessoa, verifique se o candidato não a conhece e se ela conhece o candidato.
Retorne o candidato se todas as verificações forem verdadeiras; caso contrário, -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

Armadilhas e casos extremos

Retornar o sobrevivente sem verificá-lo. Em [[0, 1], [1, 0]], o sobrevivente é uma das duas pessoas que se conhecem, e a resposta é -1.
Verificar apenas um lado. O terceiro exemplo falha apenas na linha: todos conhecem a pessoa 2, mas a pessoa 2 conhece a pessoa 3.
Contar a diagonal. matrix[c][c] é 0, então uma verificação de coluna que não ignore other == c rejeita todas as celebridades reais.
Ler a célula ao contrário. matrix[a][b] = 1 elimina a, não b. Trocar os papéis descarta a celebridade real.
Retornar um índice baseado em 1 em Lua ou R. As pessoas são numeradas a partir de 0, então subtraia 1 antes de retornar.

Perguntas frequentes3

Qual é a complexidade de tempo do problema da celebridade?

As soluções por eliminação têm complexidade de tempo O(n): n-1 consultas encontram o candidato e no máximo 2(n-1) o verificam. A versão com dois ponteiros usa espaço extra O(1), e a versão com pilha, O(n). Verificar cada pessoa em relação à definição custa O(n²).

Pode haver mais de uma celebridade?

Não. Se duas pessoas fossem celebridades, cada uma seria conhecida por todos, então cada uma conheceria a outra. Mas uma celebridade não conhece ninguém, então uma festa tem no máximo uma celebridade.

Como o problema das celebridades está relacionado a grafos?

A matriz é a matriz de adjacência de um grafo direcionado: uma aresta de i para j significa que i conhece j. Uma celebridade é um nó com grau de saída 0 e grau de entrada n-1, um sorvedouro universal. Contar os graus exige ler a matriz inteira, enquanto a eliminação encontra o sorvedouro após ler apenas O(n) células.

def findCelebrity(matrix):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

The Celebrity Problem

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada pessoa

Elimine com uma pilha

Dois ponteiros, depois verifique

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos