How to find the kth largest number in pairwise sums like setA + setB?

Question

Here are two sets of numbers, for example A and B, and we can get another set C, in which each element is the sum of the element a in and the element b from B.

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

Now I want to find out which number is the kth largest in the set C, for example, 5 is the second largest in the above example.

Is there an effective solution?

I know that pair sorting of sums is an open problem and has a smaller time limit of n ^ 2. But since only the kth number is required, perhaps we can find out from the O (n) algorithm how to find the average in an unsorted array.

Thanks.

Answer 1

If k is very close to 1 or N, any algorithm that generates the sorted sums lazily can simply be executed until the kth or Nkth element pops up.

In particular, I am thinking about the first search for the following space: (a, b) means the element ath from A, the first list added to bth from B, the second.

Keep the best = lowest priority (a, b) pairs with the cost (a, b) = A [a] + B [b].

Start with just (1,1) in the priority queue, which is minimal.

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) 

This gives you the ability to connect the comb to the pill and eliminates the need to mark each (a, b) visited in the 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 is an image of a ridge to show the successor generation rule above (you start in the upper left corner, and - in the horizontal direction):

 |------- |------- |------- 

This is simply the best research (before) of all | A | * | B | tuples and their amounts.

Note that the most likely elements pressed before popping k are 2 * k, because each element has 1 or 2 successors. Here is the possible state of the queue, where the items placed in the queue are marked * :

 |--*---- |-*----- *------- 

Everything above and to the left of the border * already displayed.

For the case of Nk<k do the same thing, but with the order of priority and reverse order of research (or just negate and change the values, get a minimum (Nk), then deny and return the answer).

See also: Sorted List of Pairwise Sums on SO or Open Problem Design .

Answer 2

Sort arrays A and B: O (mlogm + nlogn) Use a modified form of the algorithm to merge 2 sorted arrays: O (m + n) that is, at each point, u sums two elements. When u got the (m + nk + 1) th element in C, stop merging. This element is essentially the kth largest. For example. {1,2} and {3,4}: Sorted by C: {1 + 3, (1 + 4) | (2 +3), 2 + 4}

Answer 3

Well, O (n) will be the bottom border (maybe not too tight), otherwise you can run the O (n) algorithm n times to get a sorted list in O (n ^ 2).

Can you assume that the two sets are sorted (you present them in the sorted order above)? If so, you could get something with an average case that has decently improved by doing "early", starting with the last pair of elements, etc. Just guess.