2

这是一道面试题，不是作业。

N个朋友在玩游戏。他们每个人面前都有一个数字列表。

N 个朋友中的每一个从他的列表中选择一个数字并报告给游戏管理员。然后游戏管理员对上报的数字进行排序，喊出第K大的数字。

我必须计算游戏管理员可以喊出的所有可能的数字。

例如，如果 N = 3 且 K = 3，则 3 个朋友的列表是2 5 3, 8 1 6, 7 4 9。输出为 6，因为可能的值为4 5 6 7 8 9.

任何人都可以为这个问题提出一个体面的算法吗？我正在做的是创建所有可能的排列，从每个列表中取一个数字，然后对结果进行排序并打印第 k 个最大的。但这需要太多时间。

4

2 回答 2

6

要知道结果中是否存在数字，您需要知道彼此的列表是否上面有数字以及下面是否有数字。列出上面和下面都有数字的地方不是问题，因为您可以在其中选择一个适合您的数字。问题是上面只有数字或下面只有数字的列表。第一个最多只能是 NK，第二个最多只能是 K。如果不是这样，则无法选择您的号码。如果这是真的，您总是可以在列表中选择上面和下面都有数字的数字，以便选择您的号码。

这可以在线性时间内进行检查，如果您首先对列表进行排序，甚至更好，从而给出 O(n.log(n)) 的整体复杂度，其中 n 是总数。如果没有排序，你会得到 n² 的复杂度。

在您的示例中，列表：

{2 5 3}, {8 1 6}, {7 4 9}

假设我们正在寻找 2 最大的数字。对于每个号码，我们都会询问管理员是否可以喊出它。对于它们中的每一个，我们查看另一个列表中是否同时存在下方和上方的数字。让我们进一步寻找其中的一些

  • 对于 5 ：其他两个列表中的上方和下方都有数字。所以管理员可以喊“5”。

  • 对于“2”：第二个列表中的上方和下方都有数字，因此我可以在此列表中自由选择上方或下方的数字。但是第三个列表中只有上面的数字，所以这个列表中的选择数字总是更大。由于我可以在第二个列表中自由选择下面的数字，因此使我的“2”成为第二大数字。

  • 对于 "1" ：第二个列表中只有上面的数字，因此 "1" 将始终是最小的元素。

  • 对于“9”：反过来，它总是最大的。

于 2012-10-01T07:51:11.867 回答
6

从每组中取最小的数。找到其中第 K 个最大的。这是结果中的最小数字。同样，在结果中找到最大的数。证明两者之间的每个数字都在结果中。

于 2012-10-01T07:56:47.890 回答