帮着看到G家题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

帮着看到G家题

帮着看到G家题# JobHunting - 待字闺中

s*r2012-12-21 08:12

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*t2012-12-21 08:12

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*52012-12-21 08:12

3 楼

我对这道题没有很明白，能否给个解释？

【在 c********t 的大作中提到】

: 我觉得没有O（n)解
:
: A

c*t2012-12-21 08:12

4 楼

我理解是找最小的 n个 sum. sum是指 a+b

【在 M********5 的大作中提到】

: 我对这道题没有很明白，能否给个解释？

l*n2012-12-21 08:12

5 楼

有

【在 c********t 的大作中提到】

: 我理解是找最小的 n个 sum. sum是指 a+b

c*g2012-12-21 08:12

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 ?