The Celebrity Problem

Q: Quelle est la complexité temporelle du problème de la célébrité ?

Les solutions par élimination s’exécutent en temps O(n) : n-1 recherches permettent de trouver le candidat et au plus 2(n-1) de le vérifier. La version à deux pointeurs utilise un espace supplémentaire de O(1) et la version avec pile, O(n) . Vérifier chaque personne par rapport à la définition coûte O(n²) .

Q: Peut-il y avoir plus d’une célébrité ?

Non. Si deux personnes étaient toutes deux des célébrités, chacune serait connue de tout le monde, donc chacune connaîtrait l’autre. Mais une célébrité ne connaît personne, donc une fête compte au plus une célébrité.

Q: Quel est le rapport entre le problème des célébrités et les graphes ?

La matrice est la matrice d’adjacence d’un graphe orienté : une arête de i vers j signifie que i connaît j . Une célébrité est un nœud de degré sortant 0 et de degré entrant n-1 , un puits universel. Compter les degrés nécessite de lire toute la matrice, tandis que l’élimination trouve le puits après n’avoir lu que O(n) cellules.

MoyenPile Deux pointeurs Graphes

+10

Il y a n personnes à une fête, numérotées de 0 à n-1. On vous donne une matrice n × n où matrix[i][j] vaut 1 si la personne i connaît la personne j et 0 sinon. La relation de connaissance est à sens unique : i peut connaître j sans que j connaisse i.

Une célébrité est une personne que toutes les autres personnes connaissent et qui ne connaît personne. Renvoyez le numéro de la célébrité, ou -1 s'il n'y a pas de célébrité.

Fonction

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

matrixinteger-2d-array: qui connaît qui : la ligne i, la colonne j vaut 1 si la personne i connaît la personne j
Renvoieinteger: le numéro de la célébrité, ou -1 s’il n’y en a aucune

Contraintes

2 ≤ n ≤ 150, où n est le nombre de lignes et de colonnes
matrix[i][j] est 0 ou 1
matrix[i][i] = 0 pour chaque personne

Exemples

Entrée: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Sortie: 1
Explication: La ligne 1 ne contient que des zéros, donc la personne 1 ne connaît personne. La colonne 1 contient un 1 aux lignes 0 et 2, donc les deux autres personnes connaissent la personne 1. La personne 1 est la célébrité.

Pour aller plus loin

Supposons que chaque recherche soit une question que tu dois poser. Quel est le nombre minimal de questions dont tu as besoin dans le pire des cas, et peux-tu descendre en dessous de 3(n-1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Tester chaque personne par rapport à la définition nécessite environ 2n² consultations. Une cellule matrix[a][b] permet toujours d’éliminer l’un de a et b, donc n-1 consultations laissent un seul candidat. Un parcours de la ligne et de la colonne du candidat permet ensuite de déterminer s’il s’agit de la célébrité.

Vérifiez chaque personne

Intuition

La personne c est la célébrité lorsque la ligne c ne contient aucun 1 (elle ne connaît personne) et que la colonne c contient un 1 dans toutes les lignes sauf la sienne (tout le monde la connaît). Vérifiez cette définition pour chaque personne à tour de rôle et renvoyez la première qui la satisfait.

Chaque personne nécessite jusqu’à 2(n-1) consultations, soit environ 2n² au total : n = 150 signifie environ 45 000 consultations.

Algorithme

Pour chaque personne c de 0 à n-1, examinez toutes les autres personnes other.
Si matrix[c][other] vaut 1 ou si matrix[other][c] vaut 0, c n’est pas la célébrité : passez à la personne suivante.
Si aucune autre personne n’élimine c, renvoyez c.
Si toutes les personnes échouent, renvoyez -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

Éliminer à l’aide d’une pile

Intuition

Si matrix[a][b] vaut 1, a connaît quelqu’un et ne peut pas être la célébrité. Si sa valeur est 0, a ne connaît pas b, donc b ne peut pas être la célébrité. Dans les deux cas, une consultation élimine définitivement une personne. Mets tout le monde dans une pile, dépile deux personnes, pose la question et remets dans la pile celle qui reste possible : après n-1 tours, il ne reste qu’une personne.

Cette personne est une candidate, pas une réponse. L’élimination montre que personne d’autre ne peut être la célébrité, mais ne vérifie jamais la ligne et la colonne de la personne restante. Dans le troisième exemple, la personne restante est la personne 2, qui connaît la personne 3 ; la vérification renvoie donc -1. Cette vérification nécessite 2(n-1) consultations supplémentaires, soit O(n) au total.

Algorithme

Empile chaque personne.
Tant que la pile contient plus d’une personne, dépile a et b.
Si a connaît b, réempile b ; sinon, réempile a.
Prends la dernière personne comme candidate. Si elle connaît quelqu’un, ou si quelqu’un ne la connaît pas, retourne -1.
Sinon, retourne la candidate.

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

Deux pointeurs, puis vérifiez

Intuition

La pile ne contient que les personnes qui n’ont pas encore été éliminées, et leur ordre n’a pas d’importance. Remplace-la par deux pointeurs, a sur la première personne et b sur la dernière : toutes les personnes en dehors de l’intervalle de a à b sont déjà éliminées. Si a connaît b, a est éliminé ; sinon, b est éliminé. Lorsque les pointeurs se rejoignent, la personne qu’ils désignent est le candidat.

Dans le premier exemple, matrix[0][2] vaut 0, donc la personne 2 est éliminée ; puis matrix[0][1] vaut 1, donc la personne 0 est éliminée. Les pointeurs se rejoignent sur la personne 1, qui passe la vérification. Cela représente n-1 consultations, plus au maximum 2(n-1), avec deux entiers de mémoire supplémentaire.

Algorithme

Définissez a = 0 et b = n-1.
Tant que a < b : si matrix[a][b] vaut 1, ajoutez 1 à a ; sinon, soustrayez 1 à b.
Le candidat est a. Pour chaque autre personne, vérifiez que le candidat ne la connaît pas et qu’elle connaît le candidat.
Renvoyez le candidat si toutes les vérifications sont satisfaites, sinon -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

Pièges et cas limites

Renvoyer le survivant sans le vérifier. Dans [[0, 1], [1, 0]], le survivant est l’une des deux personnes qui se connaissent, et la réponse est -1.
Ne vérifier qu’un seul côté. Le troisième exemple échoue uniquement sur la ligne : tout le monde connaît la personne 2, mais la personne 2 connaît la personne 3.
Compter la diagonale. matrix[c][c] vaut 0, donc une vérification de colonne qui n’ignore pas other == c rejette toutes les vraies célébrités.
Lire la cellule à l’envers. matrix[a][b] = 1 élimine a, pas b. Inverser les rôles élimine la véritable célébrité.
Renvoyer un indice à base 1 en Lua ou en R. Les personnes sont numérotées à partir de 0, donc soustrayez 1 avant de renvoyer l’indice.

Questions fréquentes3

Quelle est la complexité temporelle du problème de la célébrité ?

Les solutions par élimination s’exécutent en temps O(n) : n-1 recherches permettent de trouver le candidat et au plus 2(n-1) de le vérifier. La version à deux pointeurs utilise un espace supplémentaire de O(1) et la version avec pile, O(n). Vérifier chaque personne par rapport à la définition coûte O(n²).

Peut-il y avoir plus d’une célébrité ?

Non. Si deux personnes étaient toutes deux des célébrités, chacune serait connue de tout le monde, donc chacune connaîtrait l’autre. Mais une célébrité ne connaît personne, donc une fête compte au plus une célébrité.

Quel est le rapport entre le problème des célébrités et les graphes ?

La matrice est la matrice d’adjacence d’un graphe orienté : une arête de i vers j signifie que i connaît j. Une célébrité est un nœud de degré sortant 0 et de degré entrant n-1, un puits universel. Compter les degrés nécessite de lire toute la matrice, tandis que l’élimination trouve le puits après n’avoir lu que O(n) cellules.

def findCelebrity(matrix):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

The Celebrity Problem

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque personne

Éliminer à l’aide d’une pile

Deux pointeurs, puis vérifiez

Pièges et cas limites

Questions fréquentes3

Problèmes similaires