Проблема знаменитости | Сет-2

Опубликовано: 20 Сентября, 2022

В группе из N человек всем известен только один человек. Такой человек может присутствовать на вечеринке, если да, то он(а) никого не знает на вечеринке. Мы можем задавать только такие вопросы, как « знает ли А Б? “. Найдите незнакомца (знаменитость) за минимальное количество вопросов.
Мы можем описать ввод задачи как массив чисел/символов, представляющих участников группы. У нас также есть гипотетическая функция HaveAcquaintance(A, B), которая возвращает true , если A знает B, и false в противном случае. Как можно решить проблему?

Также задан список know[] , где know[i] представлен в форме {a, b} означает, что человек a знает человека b .

Примеры:

Input: know[] = {{1, 3}, {2, 3}, {4, 3}}, N = 4
Output: 2
Explanation: Person with id = 3 does not know anyone, but every other person knows him.

Input: know[] = {{1, 3}, {2, 3}, {3, 2}, {4, 3}}, N = 4
Output: -1
Explanation: No celebrity is present in the party.

Подход: Наивный подход и некоторые оптимизированные подходы обсуждаются в Set-1 этой задачи.

Жадный подход: можно решить с помощью жадного подхода. Вышеупомянутая проблема может быть решена путем создания вектора bool и обхода данной матрицы следующим образом:

  • Пройдите матрицу один раз и найдите человека, который никого не знает.
  • Сохраните это как текущую знаменитость. Если текущая знаменитость — никто, верните -1, иначе перейдите к следующему шагу.
  • Снова пройдитесь по матрице и теперь проверьте, знает ли каждый человек на вечеринке текущую знаменитость.
  • Если текущая знаменитость также соответствует этому критерию, верните ее как знаменитость вечеринки.
  • В противном случае вернуть -1.

Ниже приведена реализация вышеуказанного подхода


Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ