如何找到第k人数最多的两两的款项像濑+ SETB？ [英] How to find kth largest number in pairwise sums like setA + setB?
问题描述
下面是两个整数集，说A和B 我们可以得到另一个集合C，其中的每一个元素是元素A和金额元素B B中。
Here are two integers set, say A and B and we can get another set C, in which every element is sum of element a in A and element b in B.
例如，A = {1,2}，B = {3,4}，我们得到C = {4，5，6}其中4 = 1 + 3，5 = 1 + 4 = 2 + 3 6 = 2 + 4
For example, A = {1,2}, B = {3,4} and we get C = {4, 5, 6} where 4=1+3， 5=1+4=2+3, 6=2+4
现在我想找出哪个号码是第k个最大的一组C，例如5在上面的例子中第2个规模最大的一次。
Now I want to find out which number is the kth largest one in set C, for example 5 is 2nd largest one in above example.
有一个有效的解决方案？
Is there a efficient solution?
我知道，两两款项的排序是一个开放的问题，有一个^ 2较低的时间约束。但是，由于只有第k人数最多的是需要的，也许我们可以从寻找在一个排序的数组中位数的为O（n）算法学习。
I know that pairwise sums sorting is an open problem and has a n^2 lower time bound. But since only kth largest number is needed, maybe we can learn from the O(n) algorithm of finding median number in an unsorted array.
感谢。
推荐答案
如果k是非常接近1或N，任何算法生成该排序的总和懒惰地可以简单地运行，直到第K个或N-k个项目弹出。
If k is very close to 1 or N, any algorithm that generates the sorted sums lazily could simply be run until the kth or N-kth item pops out.
在特别的，我想下面的空间的最优先搜索：（A，B）是指从A，第一个列表中的ATH项目，加入到BTH从B，第二。
In particular, I'm thinking of best-first search of the following space: (a,b) means the ath item from A, the first list, added to the bth from B, the second.
请最好=最低优先级队列对（A，B），成本（A，B）= A [A] + B [B]。
Keep in a best=lowest priority queue pairs (a,b) with cost(a,b) = A[a]+B[b].
先从只是（1,1）优先级队列中，这是最低。
Start with just (1,1) in the priority queue, which is the minimum.
Repeat until k items popped:
pop the top (a,b)
if a<|A|, push (a+1,b)
if a=1 and b<|B|, push (a,b+1)
这给你一个锯齿形梳连通性，并节省您不必标记每个（A，B）参观在数组中。注意，成本（A + 1，B）> =成本（A，B）和成本（A，B + 1）> =成本（A，B），因为A和B进行排序。
This gives you a saw-tooth comb connectivity and saves you from having to mark each (a,b) visited in an array. Note that cost(a+1,b)>=cost(a,b) and cost(a,b+1)>=cost(a,b) because A and B are sorted.
下面是一个梳子上面显示的继承生成规则的图片（你启动的左上角;一个是水平方向）：
Here's a picture of a comb to show the successor generation rule above (you start in the upper left corner; a is the horizontal direction):
|-------
|-------
|-------
这只是最好的第一口勘探（高达）全部| A | * | B |元组和他们的款项。
It's just best-first exploration of (up to) all |A|*|B| tuples and their sums.
请注意，最可能的项目推前雨后春笋般冒出k为2 * K，因为每个项目都有1或2的继任者。这里有一个可能的队列状态，在项目推入队列标记 * ：
Note that the most possible items pushed before popping k is 2*k, because each item has either 1 or 2 successors. Here's a possible queue state, where items pushed into the queue are marked *:
|--*----
|-*-----
*-------
上方和左侧一切 * 前沿已经弹出。
对于第N-k＆LT; k 的情况下，做同样的事情，但有相反的优先级队列顺序和开采秩序（或者，只是否定和扭转值，得到（NK）个最不重要的，则否定，并返回答案）。
For the N-k<k case, do the same thing but with reversed priority queue order and exploration order (or, just negate and reverse the values, get the (N-k)th least, then negate and return the answer).
See also: sorted list of pairwise sums on SO, or the Open problems project.
这篇关于如何找到第k人数最多的两两的款项像濑+ SETB？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
