The Celebrity Problem

Q: Какова временная сложность задачи о знаменитости?

Решения с исключением выполняются за время O(n) : n-1 поисков находят кандидата, а не более 2(n-1) проверяют его. Версия с двумя указателями использует дополнительную память O(1) , а версия со стеком — O(n) . Проверка каждого человека на соответствие определению требует O(n²) .

Q: Может ли быть больше одной знаменитости?

Нет. Если бы оба человека были знаменитостями, каждый был бы известен всем, а значит, каждый знал бы другого. Но знаменитость никого не знает, поэтому на вечеринке может быть не более одной знаменитости.

Q: Как задача о знаменитости связана с графами?

Матрица является матрицей смежности ориентированного графа: ребро из i в j означает, что i знает j . Знаменитость — это узел с исходящей степенью 0 и входящей степенью n-1 , универсальный сток. Подсчёт степеней требует прочитать всю матрицу, тогда как исключение позволяет найти сток, прочитав всего O(n) ячеек.

СреднеСтек Два указателя Графы

+10

На вечеринке присутствуют n человек, пронумерованных от 0 до n-1. Вам дана матрица размером n × n, где matrix[i][j] равно 1, если человек i знает человека j, и 0 в противном случае. Знакомство одностороннее: i может знать j, даже если j не знает i.

Знаменитость — это человек, которого знают все остальные и который никого не знает. Верните номер знаменитости или -1, если знаменитости нет.

Функция

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

matrixinteger-2d-array: кто кого знает: строка i, столбец j равен 1, если человек i знает человека j
Возвращаетinteger: номер знаменитости или -1, если такой нет

Ограничения

2 ≤ n ≤ 150, где n — количество строк и столбцов
matrix[i][j] равно 0 или 1
matrix[i][i] = 0 для каждого человека

Примеры

Ввод: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Вывод: 1
Пояснение: В строке 1 стоят одни нули, значит, человек 1 никого не знает. В столбце 1 единицы стоят в строках 0 и 2, значит, оба других человека знают человека 1. Человек 1 — знаменитость.

Дополнительный вопрос

Предположим, каждый поиск — это вопрос, который нужно задать. Как мало вопросов вам понадобится в худшем случае и можно ли добиться результата меньше 3(n-1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Проверка каждого человека на соответствие определению требует около 2n² обращений. Одна ячейка matrix[a][b] всегда исключает одного из a и b, поэтому после n-1 обращений остаётся единственный кандидат. Затем одна проверка строки и столбца кандидата определяет, является ли он знаменитостью.

Проверьте каждого человека

Идея

Человек c — знаменитость, если в строке c нет ни одной 1 (он никого не знает), а в столбце c во всех строках, кроме его собственной, стоит 1 (все знают его). Проверьте это определение для каждого человека по очереди и верните первого, кто ему соответствует.

Для каждого человека требуется до 2(n-1) проверок, всего около 2n²: при n = 150 потребуется около 45 000 проверок.

Алгоритм

Для каждого человека c от 0 до n-1 проверьте каждого другого человека other.
Если matrix[c][other] равно 1 или matrix[other][c] равно 0, c не является знаменитостью: перейдите к следующему человеку.
Если ни один другой человек не исключает c, верните c.
Если не подходит ни один человек, верните -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

Устранение с помощью стека

Идея

Если matrix[a][b] равно 1, a знает кого-то и не может быть знаменитостью. Если оно равно 0, a не знает b, поэтому b не может быть знаменитостью. В любом случае одна проверка навсегда исключает одного человека. Поместите всех в стек, извлеките двоих, спросите и верните в стек того, кто всё ещё может быть знаменитостью: после n-1 раундов останется один человек.

Этот человек — кандидат, а не ответ. Исключение показывает, что никто другой не может быть знаменитостью, но строка и столбец оставшегося кандидата так и не проверяются. В третьем примере остаётся человек 2, который знает человека 3, поэтому проверка возвращает -1. Проверка требует ещё 2(n-1) обращений, то есть всего O(n).

Алгоритм

Поместите каждого человека в стек.
Пока в стеке больше одного человека, извлекайте a и b.
Если a знает b, верните b в стек; иначе верните a.
Возьмите последнего человека в качестве кандидата. Если он знает кого-либо или кто-либо не знает его, верните -1.
В противном случае верните кандидата.

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

Два указателя, затем проверьте

Идея

В стеке хранятся только люди, которые ещё не исключены; их порядок не имеет значения. Замените его двумя указателями: a указывает на первого человека, а b — на последнего: все за пределами диапазона от a до b уже исключены. Если a знает b, исключается a; иначе исключается b. Когда указатели встречаются, человек, на которого они указывают, становится кандидатом.

В первом примере matrix[0][2] равно 0, поэтому человек 2 исключается; затем matrix[0][1] равно 1, поэтому исключается человек 0. Указатели встречаются на человеке 1, который проходит проверку. Это n-1 обращений плюс не более 2(n-1), при этом используется два дополнительных целых числа памяти.

Алгоритм

Задайте a = 0 и b = n-1.
Пока a < b: если matrix[a][b] равно 1, увеличьте a на 1; иначе уменьшите b на 1.
Кандидат — это a. Для каждого другого человека проверьте, что кандидат его не знает и что этот человек знает кандидата.
Верните кандидата, если все проверки пройдены; в противном случае верните -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

Ловушки и крайние случаи

Возврат выжившего без проверки. В [[0, 1], [1, 0]] выживший — один из двух людей, которые знают друг друга, поэтому ответ — -1.
Проверка только одной стороны. Третий пример не проходит проверку только по строке: все знают человека 2, но человек 2 знает человека 3.
Подсчёт диагонали. matrix[c][c] равно 0, поэтому проверка столбца, которая не пропускает other == c, отвергает каждую настоящую знаменитость.
Чтение ячейки в обратном направлении. matrix[a][b] = 1 исключает a, а не b. Если поменять роли местами, настоящая знаменитость будет отброшена.
Возврат индекса с нумерацией от 1 в Lua или R. Нумерация людей начинается с 0, поэтому перед возвратом вычтите 1.

Частые вопросы3

Какова временная сложность задачи о знаменитости?

Решения с исключением выполняются за время O(n): n-1 поисков находят кандидата, а не более 2(n-1) проверяют его. Версия с двумя указателями использует дополнительную память O(1), а версия со стеком — O(n). Проверка каждого человека на соответствие определению требует O(n²).

Может ли быть больше одной знаменитости?

Нет. Если бы оба человека были знаменитостями, каждый был бы известен всем, а значит, каждый знал бы другого. Но знаменитость никого не знает, поэтому на вечеринке может быть не более одной знаменитости.

Как задача о знаменитости связана с графами?

Матрица является матрицей смежности ориентированного графа: ребро из i в j означает, что i знает j. Знаменитость — это узел с исходящей степенью 0 и входящей степенью n-1, универсальный сток. Подсчёт степеней требует прочитать всю матрицу, тогда как исключение позволяет найти сток, прочитав всего O(n) ячеек.

def findCelebrity(matrix):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

The Celebrity Problem

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждого человека

Устранение с помощью стека

Два указателя, затем проверьте

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи