s****r
发帖数: 28 | 1 Given two sorted postive integer arrays A(n) and B(n)，each array is
decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
, b belong to B
Is there a O(n) algorithm ? |
c********t
发帖数: 5706 | 2 我觉得没有O（n)解
A
【在 s****r 的大作中提到】
: Given two sorted postive integer arrays A(n) and B(n)，each array is
: decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
: , b belong to B
: Is there a O(n) algorithm ?
|
M********5
发帖数: 715 | 3 我对这道题没有很明白，能否给个解释？
【在 c********t 的大作中提到】
: 我觉得没有O（n)解
:
: A
|
c********t
发帖数: 5706 | 4 我理解是找最小的 n个 sum. sum是指 a+b
【在 M********5 的大作中提到】
: 我对这道题没有很明白，能否给个解释？
|
l******n
发帖数: 9344 | 5 有
【在 c********t 的大作中提到】
: 我理解是找最小的 n个 sum. sum是指 a+b
|
c******g
发帖数: 1 | 6 直接用merge 有什么问题吗？
每次比较A[i]+B[j+1]和A[i+1]和B[j]
A
【在 s****r 的大作中提到】
: Given two sorted postive integer arrays A(n) and B(n)，each array is
: decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
: , b belong to B
: Is there a O(n) algorithm ?
|
s****n
发帖数: 147 | 7 感觉可以直接找a和b中Na+Nb个smallest数
Na是a中最小的若干数
Nb是b中最小的若干数
Na * Nb = n |
