/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/stacks/CelebrityFinder.java
52 строки
2 KB
Hardik Pawar
feat: Add `CelebrityFinder` new algorithm with Junit tests (#5756)
15 окт 2024, 11:48
Не верифицирован
15 окт 2024, 11:48
adf21ab
Код
Авторство
О чём код?
package com.thealgorithms.stacks; import java.util.Stack; /** * Solves the celebrity problem using a stack-based algorithm. * * <p>Celebrity is someone known by everyone but doesn't know anyone else. * <p>Applications: Graph theory and social network analysis. * * @author Hardvan */ public final class CelebrityFinder { private CelebrityFinder() { } /** * Finds the celebrity in the given party matrix using a stack-based algorithm. * * @param party A 2D matrix where party[i][j] is 1 if i knows j, otherwise 0. * @return The index of the celebrity, or -1 if there is no celebrity. */ public static int findCelebrity(int[][] party) { // Push all people onto the stack Stack<Integer> stack = new Stack<>(); for (int i = 0; i < party.length; i++) { stack.push(i); } // Find the potential celebrity by comparing pairs while (stack.size() > 1) { int person1 = stack.pop(); int person2 = stack.pop(); if (party[person1][person2] == 1) { stack.push(person2); // person1 knows person2, so person2 might be the celebrity } else { stack.push(person1); // person1 doesn't know person2, so person1 might be the celebrity } } // Verify the candidate int candidate = stack.pop(); for (int i = 0; i < party.length; i++) { if (i != candidate && (party[candidate][i] == 1 || party[i][candidate] == 0)) { return -1; } } return candidate; } }