Найди знаменитость
26 октября 2022 г.
Описание:
:::tip Следующая проблема/описание взята из Scaler и выглядит примерно так:
:::
Вы идете на вечеринку из N человек и должны найти там знаменитость.
Согласно задаче, знаменитость определяется следующим образом: знаменитость — это человек, которого все знают на вечеринке, но он никого там не знает.
Вам будет дана квадратная матрица M[][] размерами N X N. Матрица M[][] представляет людей в группе. Если для элемента строки ii и столбца j задано значение true, то i^th человек знает j^th< /сильный> человек. Обратите внимание, что здесь M[i][i] всегда будет равно нулю.
<цитата>Правило: Знаменитость известна всем, но она никого не знает на вечеринке.
Формат ввода: вам будет дана матрица M, где элементы матрицы представляют, известен ли человек другому человеку или нет. Если человек известен другому человеку, тогда M[i][j] = true, иначе он равен false.
Задача: Ваша задача узнать о знаменитости на вечеринке. Распечатайте id знаменитости, если она есть. Если на вечеринке нет знаменитости, выведите -1.
Пример Пример 1:
Input:
N = 3
M[][] = {{false true false},
{false false false},
{false true false}
}
Output: 1
Объяснение: человек с id = 1 никого не знает, поэтому в его строке отмечены все 0, тогда как все остальные люди знают человека «1». Обратите внимание, что M[0][1] = M[2][1], M[0][1]=M[2][1].
Пример 2:
Input:
N = 2
M[][] ={{false true},
{true false}
}
Output:: -1
Объяснение: Оба человека знают друг друга в группе, поэтому в группе нет знаменитостей.
Решение:
Хорошо, хорошо, честно говоря, я столкнулся с этой проблемой на собеседовании. И я решил это только методом грубой силы.
Давайте обсудим это.
Моя основная идея состоит в том, чтобы перебрать массив и проверить, знает ли этот человек кого-либо и знает ли этот человек других людей. И, очевидно, если это так, то это знаменитость.
Для этого нам нужно перебрать массив
for (int i = 0; i < n; i++)
и добавьте 2 переменные
boolean knowsAnyone = false;
boolean everyoneKnows = true;
затем мы перебираем строку и проверяем, знает ли этот человек кого-либо
for (int j = 0; j < n; j++) {
if (matrix[i][j]) {
knowsAnyone = true;
break;
}
}
На следующем шаге мы должны проверить, что этот человек известен кому-либо еще
for (int j = 0; j < n; j++) {
if (i != j && !matrix[j][i]) {
everyoneKnows = false;
break;
}
}
И, наконец, если человек никого не знает и его знают другие, значит, мы нашли знаменитость.
<цитата>Временная сложность для этого решения равна O(N*N), где N – количество людей на вечеринке.
Пространственная сложность для этого решения постоянна, поскольку мы не используем никаких дополнительных структур данных.
И интервьюер хотел другое решение без добавления хитов. Я был разочарован и не стал улучшать свою идею. К сожалению, я не прошел собеседование. Но я нашел элегантную идею.
<цитата>Эта идея называется Техника устранения
Основная идея состоит в том, чтобы удалять элементы шаг за шагом.
На первом этапе мы должны поместить всех людей в стек.
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
stack.push(i);
}
Затем мы должны перебрать стек и получить пары
while (stack.size() > 1) {
int first = stack.pop();
int second = stack.pop();
}
Когда у нас есть пара, мы можем проверить, знает ли первый человек второго
if (matrix[first][second]) {}
А если первый знает второго, значит, первый не может быть знаменитостью. Потому что знаменитость никого не знает. Но второй все же может быть знаменитостью
if (matrix[first][second]) {
stack.push(second);
} else{
stack.push(first);
}
Когда у нас нет элементов в стеке → это означает, что у нас нет знаменитости.
if (stack.empty()){
return -1;
}
Также, если у нас в стеке 1 элемент, мы должны дополнительно проверить, что все его знают, а знаменитость никого не знает
for (int i = 0; i < n; i++) {
if (i != celeb && (matrix[celeb][i] || !matrix[i][celeb])){
return -1;
}
}
И, вот и все. Это так мудро. Я был потрясен. Надеюсь, вам понравилась эта идея.
Ссылка на ресурс: https://www.scaler.com/topics/celebrity-problem/
Оригинал