Python中的名人问题

在这个问题中，我们在一个派对上。派对上有 N 个人。派对上可能有一个名人；因此，所有人都认识他或她。然而，派对上认识他的人却不认识任何人。我们只能问一个问题，例如“x 认识 y 吗？”。我们必须找到需要多少个问题才能确定名人是否存在于派对上，如果存在，那么名人是谁。

输入是一个描述派对上的人的列表。我们还将有一个预定义的函数来判断 x 是否认识 y。

让我们看一些例子来理解这个问题。

示例

输入

people = [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ]

输出 2

解释： ID 为 2 的人谁都不认识，但所有人都认识他。

输入

people = [ [0, 0, 1, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 1, 0] ]

输出： 没有名人

方法 - 1

我们将使用邻接表来解决此问题。

我们收到的是一个方阵形式的输入。设 I 为行，J 为列。该矩阵描述了人们如何认识彼此。特定行和列的所有单元格均为 0，除了代表连接的单元格。因此，如果矩阵的第 i 行和第 j 列的值为 1，则表示第 i 个人认识第 j 个人。

因此，我们可以说这个矩阵代表一个有向图，其中矩阵是图的邻接矩阵。要解决此问题，我们首先需要将矩阵转换为邻接表。这将使逻辑易于理解。如果一个人的邻接表为空，则表示这个人不认识派对上的任何人。此外，我们还需要检查派对上的所有人都认识这个人。如果这两个条件都满足，那么这个人就是名人。我们需要返回名人的索引。

我们将按照以下步骤解决问题：

• 我们将首先遍历给定的所有人矩阵，并为有向图创建一个邻接表。图的边表示 people[i][j] == 1 的条件，其中第 i 个人连接到第 j 个人；因此，第 j 个索引将被添加到第 i 个索引的邻接表中。
• 现在，我们需要使用循环遍历邻接表。循环将从索引 0 遍历到 n。
• 在每次迭代中，我们将检查第 k 个元素的邻接表是否为空。如果邻接表为空，下一步是检查第 k 个元素是否存在于所有其他人或索引的邻接表中。
• 如果第 k 个索引存在于所有列表中，那么我们的两个名人条件将得到满足，我们将返回第 i 个索引。
• 如果我们找不到满足这两个条件的任何人，我们将返回 -1。

下面是此方法的实现。

代码

输出

The celebrity at the party is: 2

时间复杂度：我们使用了嵌套循环来遍历邻接表。因此，时间复杂度是非线性的。由于 N 是邻接表的长度，最终时间复杂度将为 O(N ^ 2)。

辅助空间：我们使用了一个列表来存储邻接表，这将占用线性内存空间。因此，问题的空间复杂度为 O(N)。

方法 - 2

在此方法中，我们将使用图的入度和出度概念来解决此问题。

使用入度和出度的逻辑在于，这两个计数告诉我们节点连接到的节点以及有多少其他节点。因此，我们可以使用入度来找出有多少节点指向当前节点。

此信息或计数将告诉我们有多少人认识当前这个人。出度计数告诉我们当前节点指向了多少节点。此计数将使用当前人认识的人数。

根据我们问题，我们需要找到一个入度为 n - 1 的节点，这表示派对上的 n - 1 个人（不包括这个人自己）认识当前这个人。此外，这个人应该有 0 个出度，这表示这个人不认识派对上的任何人。让我们看看问题的算法。

以下是上述方法在 Python 中的实现。

代码

输出

The celebrity at the party is: 2