首页 > 代码库 > 两个有序数组求交集
两个有序数组求交集
采用小的在多的进行二分查找的方法。
设两个指向两个数组末尾的指针,取较小的那个数在另一个数组中二分查找,找到,则存在一个交集,并且将该目标数组的指针指向该位置前一个位置。如果没有找到,同样可以找到一个位置,使得目标数组中在该位置后的数肯定不在另一个数组中存在,直接移动该目标数组的指针指向该位置的前一个位置,再循环找,直到一个数组为空。
其实类似归并算法的merge函数,就是交替算法来填充
if a[i]<b[j]
t[num++] = a[i++];
else
t[num++] = b[j++];
这里也是,一直交替的话就能优化了
两个有序数组求交集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。