Question

如何计算两个有序整型数组的交集

Answer 1

例如，两个含有n个元素的有序（非降序）整形数组a和b（数组a和b中都没有重复元素），求出其共同元素。

a[]={0,1,2,3,4};

B[]={1,3,5,7,9};

那么它们的交集为{1,3}。

计算数组交集可以采用很多种方法，但数组的相对大小一般会影响算法的效率，所以需要根据两个数组的相对大小来确定采用的方法。

（1）对于两个数组长度相当的情况，一般可以采取以下3种方法。

方法一：采用二路归并来遍历两个数组。(这个名字好霸气，有木有武功招数的赶脚）

设两个数组分别为array1[n1]和array2[n2],分别以i、j从头开始遍历两个数组。在遍历过程中，如果当前遍历位置的array1[i]与array2[j]相等，则此数为两个数组的交集，记录到随便array1或array2中，并继续向后遍历array1和array2.如果array1[i]>array2[j]，则需继续向后遍历array2.如果array1[i]小于array2[j]，则需要继续向后遍历array1，直到有一个数组结束遍历即停止。总的来说，就是谁落后了，谁的下标就自增去吧。

代码如下：

#include "stdafx.h"
#include <stdio.h>
void mixed(int array1[], int n1, int array2[], int n2)
{
int i = 0, j = 0, k = 0;
while (i < n1&&j < n2)
{
if (array1[i] == array2[j])
{
array1[k] = array1[i];
printf("%d\n", array1[k]);
i++;
j++;
k++;
}
else if (array1[i]>array2[j])
{
j++;
}
else if (array1[i] < array2[j])
{
i++;
}
}
}
void main()
{
int a[] = { 0, 1, 2, 3, 4 };
int b[] = { 1, 3, 5, 7, 9 };
mixed(a, 5, b, 5);
getchar();
}

　　效果如图：

方法二：顺序遍历两个数组，将数组元素存放到哈希表中，同时对同级的数组元素进行计数。如果为2，则为两者的交集元素。

方法三：遍历两个数组中任意一个数组，将遍历得到的元素存放到哈希表，然后遍历另外一个数组，同时对建立的哈希表进行查询，如果存在，则为交集元素。

（2）对于两个数组长度相差悬殊的情况，如数组a的长度远远大于数组b的长度，则可以采用下面几种方法。

方法一：依次遍历长度小的数组，将遍历得到的数组元素在长数组中进行二分查找。具体而言，设两个指向两个数组为元素的指针，取较小的那个数在另一个数组中二分查找，找到，则存在一个交集，并且将该目标数组的指针指向该位置前一个位置。如果没有找到，同样可以找到一个位置，使得目标数组中在该位置后的数肯定不在另一个数组中存在，直接移动该目标数组的指针指向该位置的前一个位置，再循环找，直到一个数组为空为止。因为两个数组中都可能出现重复的数，因此二分查找时，当找到一个相同的数x时，其下标为i，那么下一个二分查找的下界变为i+1，避免x重复使用。

方法二：采用与方法一类似的方法，但是每次查找在前一次查找的基础上进行，这样可以大大缩小查找表的长度。

方法三：采用与方法二类似的方法，但是遍历长度小的数组的方式有所不同，从数组头部和尾部同时开始遍历，这样可以进一步缩小查找表的长度。