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 |