{Algo}一道百度面试题

[pongba]

转自cpper：http://www.cpper.com/c/t4873.html

给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[黑罗伊]

如果a和b都是有序的就好办多了

[Kyle M. Lee]

pongba 写道:

> 转自cpper：http://www.cpper.com/c/t4873.html
>
> 给定两个数组：
> int a[] = {a1,a2,a3,...,an};
> int b[] = {b1,b2,b3,...,bn};
> 给定一个数B
> 要求：
> 1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
> 2. 复杂度为O(n+k) k为数据对的个数。
>

二维数组？

[heroboy]

可以用基数排序啊，复杂度差不多是O（n）

On Jun 27, 12:59 am, 黑罗伊 <royleegal...@gmail.com> wrote:
> 如果a和b都是有序的就好办多了