名人问题

在本教程中，我们将学习名人问题。我们将使用各种方法来解决这个问题。这是一个重要的编程问题，可能会在技术面试中出现。本教程将帮助您学会高效地解决它。让我们来理解问题陈述。

派对上有 N 个人，只有一个人被所有人认识，但这个人不认识任何人。我们需要找出 A 是否认识 B，换句话说，我们需要用尽可能少的问题来识别这个“陌生人”或“名人”。

这个问题由一组数字或字符表示，象征着派对上的人。我们有一个名为 HaveAcquaintance(A, B) 的函数，当给定两个人 A 和 B 时，它会告诉我们 A 是否认识 B（返回 true）或者不认识（返回 false）。

示例 1

输入

矩阵 = [[0, 0, 1, 0, 1],

[0, 0, 1, 0, 0],

[0, 1, 0, 1, 1],

[0, 0, 1, 0, 0],

[0, 1, 1, 0, 0]]

输出： id = 3

解释： 在这种情况下，ID 为 3 的人不知道任何人，而每个人都认识他。

示例 2

输入

矩阵 = [[0, 0, 1, 0, 1],

[0, 0, 1, 0, 0],

[0, 1, 0, 1, 1],

[0, 0, 1, 0, 1],

[0, 1, 1, 0, 0]]

输出： 没有名人

解释： 在这种情况下，没有名人。

基本方法和利用邻接表的方法

我们有一个 NxN 的方阵 M[][] 来表示派对上的人之间的关系。在此矩阵中，如果 M[i][j] 设置为 1，则表示第 i 个人认识第 j 个人。我们将此视为一个有向图并构建一个邻接表。然后，我们检查是否有人拥有空的邻接表，这表明他们不认识派对上的任何人。如果是这种情况，我们验证是否派对上的所有其他人都认识那个人。如果他们认识，我们将该人视为名人并返回其索引 i。如果不是，我们将继续寻找名人。

要解决此问题，请按照以下步骤操作

1. 首先，我们遍历给定的矩阵并创建一个邻接表。
2. 如果 M[i][j] 为 1，则在邻接表中从 person i 到 person j 添加一个有向边。
3. 接下来，从 0 迭代到 n（派对上的人数）。
4. 检查 person i 的邻接表是否为空。
5. 如果为空，请检查派对上的所有人是否都认识 person i。
6. 如果所有其他人都有指向 person i 的连接，则将他们视为名人并返回他们的索引 i。如果找不到名人，则继续搜索。

让我们理解以下示例 -

示例 -

输出

2

解释 -

在上面的代码中，我们遵循了以下步骤 -

1. 我们定义了 findCelebrity() 函数，该函数以矩阵 M 作为输入，获取矩阵 M 的大小以确定派对上的人数 (N)。然后，我们将 n 初始化为矩阵的行数（或列数）。
2. 之后，我们创建一个空列表 `adj` 来表示邻接表。此列表的每个元素将包含对应人员认识的人员列表。
3. 然后，我们根据矩阵 `M` 中的值填充邻接表 (adj)。对于每个单元格 `M[i][j]`，其中 `M[i][j] == 1`，这意味着人员 `i` 认识人员 `j`，因此我们将 `j` 添加到人员 `i` 的邻接表中。
4. 我们遍历每个人，用索引 i 从 0 到 n-1 表示。
5. 对于每个人 i，检查其邻接表是否为空。空的邻接表意味着人员 i 不认识派对上的任何人。
6. 如果人员 i 的邻接表为空，则意味着人员 i 可能是名人。为了确认，我们检查派对上的所有其他人是否认识人员 i。
7. 我们遍历所有其他人（用 `j` 表示）从 0 到 n-1。如果 i 不等于 j 且 j 不在人员 i 的邻接表中，则意味着人员 j 不认识人员 i。在这种情况下，我们可以得出结论，人员 i 不是名人。
8. 如果在检查了所有其他人之后，我们发现没有人认识人员 `i`，我们将人员 `i` 视为名人并返回其索引，即 `i`。如果在检查了所有人之后仍未找到名人，则返回“没有名人”。

名人问题：利用图进行识别

请按照以下步骤解决此问题

1. 我们创建两个数组，indegree 和 outdegree，以跟踪入站和出站连接的数量。
2. 然后我们使用两个嵌套循环：外层循环从 0 迭代到 n，内层循环也从 0 迭代到 n。
3. 对于每一对个人 i 和 j，执行以下检查
   1. 如果 i 认识 j，则增加 i 的出度 (outdegree) 和 j 的入度 (indegree)。
   2. 如果 j 认识 i，则增加 j 的出度 (outdegree) 和 i 的入度 (indegree)。
4. 运行一个从 0 到 n 的循环，找到入度为 n-1（表示此人被其他人认识）且出度为 0（表示此人不认识任何人）的个人 ID。

让我们来理解以下代码——

示例 -

输出

The celebrity is person with ID 2

解释 -

让我们理解上面的代码

1. 我们初始化 indegree 和 outdegree 数组来跟踪认识每个人的人数以及他们认识的人数。
2. 然后我们使用两个嵌套循环遍历每一对个人 (i, j)。这些循环代表派对上的每一对可能的个人。
3. 对于每一对 (i, j)。我们通过检查 MATRIX[i][j] 来确定人员 i 是否认识人员 j。如果 MATRIX[i][j] 为 1，则表示人员 i 认识人员 j。
4. 如果人员 i 认识人员 j，则递增人员 i 的出度 (outdegree) 和人员 j 的入度 (indegree)。此步骤有助于跟踪每个人的认识情况以及每个人被认识的情况。
5. 处理完所有对 (i, j) 后，将填充 `indegree` 和 `outdegree` 数组。
6. 我们遍历所有个人（从 0 到 n）并检查是否有任何个人满足成为名人的条件
7. 我们检查他们的入度是否等于 `n - 1`。如果等于，则表示所有其他人认识此人，因为名人应该被除自己以外的所有人认识。
8. 检查他们的出度是否为 0。这意味着该人不知道派对上的任何人。
9. 如果找到满足这些条件的个人，则认为他们是名人，并返回其 ID。
10. 如果在检查了所有个人后仍未找到名人，则代码返回 -1，表示派对上没有名人。

使用递归

我们可以使用递归来解决这个问题。如果知道了 N-1 个人的潜在名人，就有可能从它找到 N 的解决方案。潜在名人是通过以下规则移除 n-1 个人后仍然存在的人。

• 如果 A 认识 B，则 A 不可能是名人，但 B 可能是。
• 如果 B 认识 A，则 B 不可能是名人，但 A 可能是。

以下是实现递归的步骤 -

1. 首先，我们创建一个接受整数 n 作为输入的递归函数。
2. 我们检查基本情况：如果 n 等于 0，则返回 -1。
3. 我们调用递归函数处理前 n-1 个元素，以找到潜在名人的 ID。
4. 如果步骤 3 返回的 ID 为 -1，则将 n 指定为潜在名人的 ID 并返回 n。
5. 如果前 n-1 个元素的潜在名人认识 n-1（使用 0 基索引），则返回 n-1。
6. 如果前 n-1 个元素的名人不认识 n-1，则返回 n-1 个元素的名人 ID（使用 0 基索引）。
7. 如果步骤 4、5 和 6 中的任何条件都不适用，则返回 -1。
8. 然后，创建一个包装函数，并检查递归函数返回的 ID 是否确实是名人。

让我们理解下面的代码片段。

示例 -

输出

Celebrity ID: 2

结论

在此代码中，我们通过检查某人是否不认识任何人但被所有人认识来找到派对上的名人。我们使用两个数组 indegree 和 outdegree 来跟踪谁认识谁以及被谁认识。通过比较这些值，我们识别出名人。如果存在这样一个人，则返回其 ID。如果不存在，则得出结论，派对上没有名人。此代码可以有效地解决名人问题，这是技术面试轮中常见的面试问题。