这是一个面试问题,而不是作业.
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个最大的数字.但这需要太多时间.
要知道结果中是否存在数字,您需要知道每个其他列表是否有上面的数字以及下面是否有数字.列出上面和下面都有数字的列表不是问题,因为你可以在它们中选择一个适合你的数字.问题是只有上面的数字或下面只有数字的列表.第一个必须至多为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":这是另一种方式,它总是最大的.