f*********d
发帖数: 140 | 1 两个排序好的数组 求和最小的m个pair
eg
input
A = 1 2 4 5 6
B = 3 5 7 9
m = 3
output
1, 3
2, 3
1, 5 | l*****a
发帖数: 14598 | 2 这个我会
minimum tree,
1) insert A[0] B[0]
2) pop up the smallest, insert A[1]B[0],A[0]B[1]
3) pop up the smallestA[i]B[j] , insert A[i+1]B[j],A[i]B[j+1]...
until u get m
a tricky point is create an array C[m]=n
mean for A[m], you already used A[m]B[n]
you can use this to avoid dup
【在 f*********d 的大作中提到】
: 两个排序好的数组 求和最小的m个pair
: eg
: input
: A = 1 2 4 5 6
: B = 3 5 7 9
: m = 3
: output
: 1, 3
: 2, 3
: 1, 5
| k*******t
发帖数: 144 | 3 请问什么是minimum tree, 只查到了minimum spanning tree, 给个link也行。
【在 l*****a 的大作中提到】
: 这个我会
: minimum tree,
: 1) insert A[0] B[0]
: 2) pop up the smallest, insert A[1]B[0],A[0]B[1]
: 3) pop up the smallestA[i]B[j] , insert A[i+1]B[j],A[i]B[j+1]...
: until u get m
: a tricky point is create an array C[m]=n
: mean for A[m], you already used A[m]B[n]
: you can use this to avoid dup
| l*****a
发帖数: 14598 | 4 sorry that should be heap
【在 k*******t 的大作中提到】
: 请问什么是minimum tree, 只查到了minimum spanning tree, 给个link也行。
| z******g
发帖数: 5 | 5 1, 3
2, 3
1, 5
how about 1,5 pair ? | l*****a
发帖数: 14598 | 6 what will it be if not 1,5
【在 z******g 的大作中提到】
: 1, 3
: 2, 3
: 1, 5
: how about 1,5 pair ?
| f*********d
发帖数: 140 | 7 你的算法可能过早的把不该谈出的数过早的谈出
比如A中的1， 后面可能跟5配对组成一个pair~
【在 l*****a 的大作中提到】
: what will it be if not 1,5
| l*****a
发帖数: 14598 | 8 算法只弹出pair
不会弹出单个的
【在 f*********d 的大作中提到】
: 你的算法可能过早的把不该谈出的数过早的谈出
: 比如A中的1， 后面可能跟5配对组成一个pair~
| f*********d
发帖数: 140 | 9 1 3 弹出来了 怎么得到 1， 5 呢？
【在 l*****a 的大作中提到】
: 算法只弹出pair
: 不会弹出单个的
| f*********d
发帖数: 140 | | | | u*****o
发帖数: 1224 | 11 我也觉得得用HEAP。是不是可以这样呢？
1。建一个size是m的max-heap. 先push进去sum of A[0]+B[0], A[0]+B[1], ....A[0]+
B[m-1]这
个题就是1+3,1+5,1+7.
2。然后从A[1]开始,开始比较A[1]+B[0],A[1]+B[1]...A[1]+B[m-1]（2+3，2+5，2+7）
这些和和heap里面的数大小。如果A[1]+B[0]已经大过现在heap max(1+7), 直接output
3. 如果不，这个题就是2+3 < 1+7, pop out current max, push in 2+3, 重新sort
heap, 现在max 是1+5，再拿2+5和1+5比，外面的2+5大，直接output,要不再一轮的pop
, sort and push..
这个最好时间是m, 最差可能是m^2, 时间应该不是最优吧。。。
【在 f*********d 的大作中提到】
: 两个排序好的数组 求和最小的m个pair
: eg
: input
: A = 1 2 4 5 6
: B = 3 5 7 9
: m = 3
: output
: 1, 3
: 2, 3
: 1, 5
| N*****Z
发帖数: 70 | 12 max heap吧
【在 l*****a 的大作中提到】
: 这个我会
: minimum tree,
: 1) insert A[0] B[0]
: 2) pop up the smallest, insert A[1]B[0],A[0]B[1]
: 3) pop up the smallestA[i]B[j] , insert A[i+1]B[j],A[i]B[j+1]...
: until u get m
: a tricky point is create an array C[m]=n
: mean for A[m], you already used A[m]B[n]
: you can use this to avoid dup
| l*****a
发帖数: 14598 | 13 1) insert A[0] B[0]
2) pop up the smallest, insert A[1]B[0],A[0]B[1]
【在 f*********d 的大作中提到】
: 1 3 弹出来了 怎么得到 1， 5 呢？
| l*****a
发帖数: 14598 | 14 每次不是找最小的吗？
【在 N*****Z 的大作中提到】
: max heap吧
| f*********d
发帖数: 140 | 15 嗯 是的~
学习了！
【在 l*****a 的大作中提到】
: 1) insert A[0] B[0]
: 2) pop up the smallest, insert A[1]B[0],A[0]B[1]
|
|
