这是一个面试问题，而不是一门功课。

每个N个朋友选择一个号码，从他的名单，并上报给游戏管理员。然后游戏管理员排序报告的数字和呐喊第K个数量最多。

我必须计数所有可能的数字，游戏管理员可以留言。

例如，如果N = 3和K = 3，而对于3个朋友的列表是 2 5 3 ， 8 1 6 ， 7 4 9 。输出是6，因为可能的值是 4 5 6 7 8 9 。

任何人都可以提出一个体面的算法，这个问题？我在做什么是创建以一个数字从每个列表，然后排序得到的和打印第k大所有可能的排列。但是，这需要太多的时间。

要知道，如果一个数字是present在结果还是没有，你需要知道对方列表中，如果有上面的，如果有号码下面的数字。列表，上面有数字和下面不是一个问题，因为你可以，因为它适合你选择在其中一个号码。问题是那里只有数字的上方或下方只有数字列表。第一那些必须至多NK，所述第二组必须至多K。如果这是不正确的，你的电话号码不能被拾取。如果这是真的，你总是可以选择在那里有两个号码的上方和下方，使您的号码选择了清单数字。

这可以在线及时检查，甚至更好，如果你的第一个排序的名单，从而使邻其中n为总人数的数量总体复杂性（n.log（N））。不排序你有N²复杂性。

在与列表您的例子：

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

说，我们正在寻找的2-最多。对于每一个数字，我们问是不是可以喊的administator。对于每个人，我们看，如果在其他目录下面有两个数字和数字以上。让我们来看看另外一些人

有关5：有数字的上方和下方的两个其他列表。因此，5，可以喊管理员。

有关2：有数字的上方和下方的第二个列表，所以我可以自由选择高于或低于这个列表中的号码。但也有只有数字上述在第三列表中，所以在此列表中的拾取数量将总是更大。因为我可以自由地选择一些低于第二个列表，从而使我的2的第二个最大数量。

有关1：只有数字在上面的第二个列表，因此1永远是最小的元素

有关9：这是倒过来的，它始终是最伟大的

This is an interview question, not a homework.

N friends are playing a game. Each of them has a list of numbers in front of himself.

Each of N friends chooses a number from his list and reports it to the game administrator. Then the game administrator sorts the reported numbers and shouts the K-th largest number.

I must the count all possible numbers that the game administrator can shout.

For example, if N = 3 and K = 3, and the lists for the 3 friends are 2 5 3, 8 1 6, 7 4 9. The output is 6, since the possible values are 4 5 6 7 8 9.

Can anybody suggest a decent algorithm for this problem? What I am doing is to create all possible permutations taking one number from each list, then sorting the resultant and printing the kth-largest. But that takes too much time.

To know if a number is present in the result or not, you need to know for each other list if there are numbers above and if there are numbers below. List where there are both numbers above and below are not a problem as you can choose a number in them as it suits you. The problem are lists where there are only numbers above or only numbers below. The first ones must be at most N-K, the second ones must be at most K. If this is not true, your number cannot be picked. If this is true, you can always choose numbers in the lists where there are both number above and below so that your number is picked.

This can be checked in linear time, or even better if your first sort your lists, thus giving an overall complexity of O(n.log(n)) where n is the number of numbers in total. Without sorting you got a n² complexity.

In your example with lists :

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

say we are looking for the 2-greatest number. For each number we ask if it can be shout by the administator. For each of them we look if in the other list there are both numbers below and numbers above. Let's look further for some of them

For 5 : there is numbers above and below in both other lists. So "5" can be shout by the administrator.

For "2" : there is numbers above and below in the second list so I can freely choose a number above or below in this list. But there are only numbers above in the third list, so the picked number in this list will always be greater. Since i can freely choose a number below in the second list, thus making my "2" the 2nd greatest number.

For "1" : there is only numbers above in the second list, so "1" will always be the smallest element.

For "9" : this is the other way round, it is always the greatest.