v******a
发帖数: 54 | 1 Given two sorted arrays A, B, find the m pairs with the smallest sums.
For example: A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
m=3
Results(1, 3),(2, 3),(1, 5)
看了以前大家的讨论，
最好的complexity是多少？
貌似有一个DP的，怎么做？ | I**A
发帖数: 2345 | 2 I think that one is different from this one though I don't remember what
that one is?
For this one, since we only need m pairs, we can select the first m elements
from both A and B (if less than m, then choose the whole array), name them
as A' and B'
The algorithm that I can think of is for each element in A', add it with
each of the elements of B', meanwhile, keep a edited max heap to maintain
the m smallest sum value (of course, we need to keep the element values as
well). Since the arrays are
【在 v******a 的大作中提到】
: Given two sorted arrays A, B, find the m pairs with the smallest sums.
: For example: A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
: m=3
: Results(1, 3),(2, 3),(1, 5)
: 看了以前大家的讨论，
: 最好的complexity是多少？
: 貌似有一个DP的，怎么做？
| h**6
发帖数: 4160 | | I**A
发帖数: 2345 | | P********l
发帖数: 452 | |
|
