我想问下这个问题的算法（C语言）

来源：百度知道 编辑：UC知道 时间：2024/05/18 18:28:28
有两组int数，每个数组有5000个元素，S1[5000],S2[5000]
两个数组的数都已经按照从小到大的顺序排列了。
要找出两个数组中相等的元素。。
请告诉我效率高一点的算法。。
谢谢
四楼是指哪个方法～
三楼的么～嗯～其实我也觉得三楼的是很好的。。

我觉得用2个指针，分别依次取两个数组最前一个元素，比较取值：小的值对应的指针自增，继续比；相等输出并两指针都自增；任意一方指针到达数组末尾结束；最坏扫描10000次（2n），最好扫描5000次（n）

虽然顺序扫描效率不是很高，但控制在O（n）凑合吧

int k = 0;
for(int i = 0;i<5000,k<4999;i++)
{
在这里用S2[i]去二分查找S1[k]到S1[5000]
}
//k为上次循环二分查找时最后一个位置
主要是保存上次匹配(无论成功与否)最后的一个位置.下次直接就从它开始到4999就 OK了
//下面那朋友说那点很好哈

补充一点 掐头 去尾 从共同段里找
关注......................

其实这是一个模式匹配的问题,去看看数据结构的书,这个是最快的.