如何取两个已排序数组的交集

Python012

如何取两个已排序数组的交集,第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()

}

数组求交集的方法

1.暴力搜索

2.利用HashMap

3.先排序再用两个指针查找

4.位图法

5.大文件求交集用分治法，组内用位图法

一维数组取交集是非常的简单，直接用一个函数即可。array_intersect($arr, $ar)，那么二维数组又是如何的取出它们的交集呢，可能有人同样想用这个函数，但结果却不是我们想要的。下面有这样的一个数组：

$arr=array(

array('a'=>'1',2),

array(3,4)

)

$ar=array(

array('a'=>1,2),

array(3,4)

)

如果我单独用 array_intersect($arr, $ar)。返回的结果如下：

array(

array('a'=>'1',2),

array(3,4)

)