The Celebrity Problem in Java

名人问题是一个经典的谜题，在计算机科学领域，尤其是在算法问题解决方面，经常会遇到。这个问题可以概括如下。

想象一个有 N 个人的派对。“名人”是指每个人都认识，但自己不认识任何其他人的人。目标是确定是否有任何参与者是名人。

解决这个问题的关键条件

1. 如果 A 认识 B，那么 A 不可能是名人。
2. 如果 A 不认识 B，那么 B 不可能是名人。

问题陈述

给定一个 N x N 的 矩阵 M

• M[i][j] == 1 表示 i 认识 j。
• M[i][j] == 0 表示 i 不认识 j。

任务是以高效的方式识别名人（如果存在）。

示例

让我们考虑以下 4 个人的矩阵 M



在这里，3 号是名人，因为

• 每个人都认识 3 号。
• 3 号不认识任何人。

让我们通过不同的方法来解决这个问题。

蛮力法

一种简单的方法是检查每个人。对于每个人

• 验证他们是否被其他人认识。
• 验证他们是否不认识任何人。

这种方法需要 O(N²) 的时间，因为对于每个人，您都需要检查他们与其他所有人的关系。

优化方法：基于堆栈的解决方案

一种更有效的方法可以使用堆栈将问题的时间复杂度降低到 O(N)。

步骤 1： 将所有人推入堆栈。

步骤 2： 连续弹出两个人，例如 A 和 B

• 如果 A 认识 B，那么 A 不可能是名人；将 B 推回堆栈。
• 如果 A 不认识 B，那么 B 不可能是名人；将 A 推回堆栈。

步骤 3： 所有比较完成后，只剩一个人。这是潜在的名人。

步骤 4： 验证此人是否满足名人条件

• 他们被所有人认识。
• 他们不认识任何人。

让我们在 Java 程序中实现上述方法。

文件名：CelebrityProblem.java

import java.util.Stack; public class CelebrityProblem { // Sample matrix static int[][] M = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0} }; // Function to check if person a knows person b static boolean knows(int a, int b) { return M[a][b] == 1; } // Function to find the celebrity public static int findCelebrity(int n) { Stack<Integer> stack = new Stack<>(); // Step 1: Push all people onto the stack for (int i = 0; i < n; i++) { stack.push(i); } // Step 2: Determine the potential celebrity while (stack.size() > 1) { int a = stack.pop(); int b = stack.pop(); if (knows(a, b)) { // a knows b, so a can't be the celebrity stack.push(b); } else { // a doesn't know b, so b can't be the celebrity stack.push(a); } } // Step 3: Verify the potential celebrity int candidate = stack.pop(); for (int i = 0; i < n; i++) { if (i != candidate) { // Candidate should be known by everyone if (!knows(i, candidate)) { return -1; } // Candidate should not know anyone if (knows(candidate, i)) { return -1; } } } return candidate; } public static void main(String[] args) { int n = 4; // Number of people int result = findCelebrity(n); if (result == -1) { System.out.println("No celebrity found"); } else { System.out.println("Celebrity found at index: " + result); } } }

输出

 
Celebrity found at index: 3   

解释

该程序使用基于堆栈的方法来识别名人。首先，所有人都被推入一个 堆栈。然后通过比较两个人来缩减堆栈：如果 A 认识 B，则 A 不是名人，因此将 B 推回堆栈；否则，B 不是名人，将 A 推回。这个过程一直持续到只剩一个候选人。

然后通过检查每个人是否认识他们以及他们是否不认识其他人来验证候选人。如果候选人满足这些条件，则他们是名人；否则，不存在名人。此解决方案的时间复杂度为 O(N)，可以有效地解决任何数量的与会者的问题。

复杂度分析

时间复杂度：O(N)

堆栈缩减涉及 N-1 次比较。验证步骤需要检查 2N 个条件（N 个入站关系，N 个出站关系）。

空间复杂度： O(N) 用于堆栈。

结论

名人问题展示了高效的问题解决技术，突出了如何通过算法优化来改进暴力解法。Java 实现说明了在实际编码场景中如何处理此类问题。

---

下一个主题Java 中的霓虹数



← 上一个 下一个 →