题目描述

找出两个数组中相同的数字。

输入格式

第一行两个整数 N , M ，分别代表两个数组的数字个数 （1 <= N , M <= ${10}^6$ )。

第二行 N 个各不相同的整数，( 0 <=每个整数 <= ${10}^9$ ，为了简化问题，这 N 个数已经从小到大排序）。

第三行 M 个各不相同的整数，( 0 <=每个整数 <= ${10}^9$ , 这 M 个数已经从小到大排序）。

输出格式

一行用空格隔开的整数，按照从小到大的顺序输出两个数组中相同的数字。

样例

7 10
3 5 6 7 8 12 15
2 4 6 9 10 12 16 17 18 19

6 12

笨方法

基于两层循环暴力枚举，第一层循环枚举第一个数组里的数，第二层循环是去第二个数组里面找这个数，最终的计算复杂度是 O(N*M) ，题目说了 N，M 的范围是 ${10}^{12}$，所以一定超时的。但是，掌握这个笨方法有利于理解后面的好办法。

#include<bits/stdc++.h>
using namespace std;
int x[1000001],y[100001];
int main()
{
	int n,m,i,j;

	scanf("%d%d",&n,&m);
	
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);

	for(i=1;i<=m;i++)
		scanf("%d",&y[i]);

	for(i=1;i<=n;i++)  //枚举第一个数组里面的各个数 
	{
		for(j=1;j<=m;j++)  //到第二个数组里面去找，看能否找得到 
		{
			if(x[i]==y[j])
				printf("%d ",x[i]);
			//题目说了，数组内是没有重复的数的，所以找到了之后不需要打标记，不会出现重复答案的 
		}
	}

	return 0;
}

双指针算法

我们仔细看上述笨方法代码，存在着几可以改善的地方：

1. 我们去找 y[ ] 数组找 $x_i$ , 以样例数据为例, x[1] = 3 , 其实找到 y[2] = 4 的时候已经没有必要找下去了，因为 y[2]> x[1] ， 而后面的 y[j] 会比 y[2] 更大，更加不可能找得到的一个 y[j] = 3

2. x[3] = 6 , 能找到 y[3] = 6 ,之后开始找 x[4] = 7 , 这时候其实不需要从 y 数组的最开始开始找，因为 x[4] 肯定比 x[3] 大，找 y[j] = x[3] 的时候已经找到了 j = 3 这个位置 , 找一个比 x[3] 更大的数字不可能在前面更小的 y[j] 那里找到。

3. 用 i 变量记录第一个数组比较到什么位置， 用 j 变量记录第二个数组比较到什么位置，习惯上，我们叫这种指向下标位置的变量称为 指针 ，指针这个概念在其它场合可能有不同的意思（ C++语法特性提供了指向变量的内存地址，所以一些讲语法的文章讲的指针很可能是讲这个内存地址 ）

4. 一开始 i = j = 1，这时候就是最小的 $x_i$ , $y_i$，之后，每次比较 $x_i$ ，$y_j$，根据不同情况移动 i , j 指针。

   1. 如果 $x_i$ > $y_j$ ，说明 $y_j$ 小了，需要找更大的 $y_j$，因此往右推动 j 指针 ,j++
   2. 如果 $x_i$ < $y_j$ , 说明 $x_i$ 小了，需要找更大的 $x_i$，因此往右推动 i 指针 ,j++
   3. 如果 $x_i$ = $y_j$ , 匹配成功，按照题目要求做相应的事情，往右推动 i 指针和 j 指针， i++,j++

5. 当 i 或者 j 任何一个指针超出了有效范围，就不用找下去了。

基于这个指针移动的算法，每一次循环起码会让 i 或者 j 加一，如果匹配成功，是两个都加一。所以，计算复杂度是 O(m+n)。

结合样例数据，整个比较过程可以用下面的图表展示：

程序填空

#include<bits/stdc++.h>
using namespace std;
int x[1000001],y[100001];
int main()
{
	int n,m,i,j;

	scanf("%d%d",&n,&m);
	
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);

	for(i=1;i<=m;i++)
		scanf("%d",&y[i]);

	i=j=1;

	while(填空(1) && 填空(2)) //第一个空围绕 i 来填；  第一个空围绕 j 来填；
	{
		if(x[i]<y[j])
			填空(3);
		
		else if(x[i]>y[j])
			填空(4);
		else
		{
			printf("%d ",x[i]);
			填空(5); 
			填空(6);
		}
	}

	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}

填空(6): {{ input(6) }}