2008-06-13
|
 | 超级版主 | | 注册日期: 2002-09-03
帖子: 3,138
| |
 回复: 据说是百度的面试题
引用:
作者: sankt  偶再来补充一题：
给定两个数组：
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为数据对的个数； | a和b没有别的条件？假设都不是排序的，那么：
1.a里面都是1，b里面也都是1。B也是1。
2.a里面都是1，b里面也都是0。B也是1。
那么，情况2有n^2个结果。而情况1是0个结果。但是乱序情况下，我看不出1和2有啥大区别。而一旦排序，那么就是O(nlgn)了。 |