读书人

两个排序数组怎么求交求最优算法和

发布时间: 2013-11-18 00:11:49 作者: rapoo

两个排序数组,如何求交,求最优算法和分析
PS:另外问下STL中的求交算法是如何实现的?
[解决办法]
数组A和迭代i
数组B和迭代j

i和j都从0开始迭代,如果A[i] == B[j] , OK, i 和 j 一起自增
A[i] < B[j]说明 i 走的慢了,自增,反之就是 j 慢了,自增

Length(A) + Length(B) 的复杂度,遍历一次就行。

比的时候用二分法代替线性方案来缩小数组A和B的范围也可以,但貌似会有退化行为,
变成2NlgN了
[解决办法]
看STL源码剖析吧!这本书还可以的!

读书人网 >C++

热点推荐