首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

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

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

两个排序数组,如何求交,求最优算法和分析
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源码剖析吧!这本书还可以的!

热点排行