兩個數組取交集演算法

『壹』 c語言求兩個數組的並交集

只簡單地分析了一下交集的情況，求並集類似。網路知道這個代碼支持不怎麼好，復制粘貼到 vs 之類的代碼編輯器裡面縮進一下會比較好看。

見代碼如下：

#include <stdio.h>

#include <stddef.h>

#include <stdlib.h>

#include <time.h>

// 使用整型數組為例，其它數組同理

// 交集

// 通過迭代遍歷判斷相同元素，時間復雜度較高，平方量級

// 傳入原數組及其長度、結果數組

// 返回結果數組的長度

// （需要自行保證結果數組足夠大）

size_t getIntersection(array1, array1_len, array2, array2_len, result_array)

int* array1, * array2, * result_array;

size_t array1_len, array2_len;

{

size_t result_p = 0;

for (size_t i = 0; i < array1_len; ++i)

{

for (size_t j = 0; j < array2_len; ++j)

{

if (array1[i] == array2[j])

{

result_array[result_p++] = array1[i];

break;

}

}

}

return result_p;

}

// 另一種思路是用快速排序等高效的排序演算法先將數組排序，

// 然後再遍歷一次數組，這時因為已經排好序了，所以最多隻要

// 遍歷 array1_len + array2_len 即可，此時時間復雜度較低，

// 因為快速排序等一般是 nlog(n)，然後後面接一個一次量級的遍歷，

// 總的來說是 nlog(n) + n，也就是 nlog(n)，比 n^2 要快一些。

int intAscendingComparor(const void* left, const void* right)

{

return *(int*)left - *(int*)right;

}

// 交集

// 先排序後遍歷判斷相同元素，時間復雜度較低

// 傳入原數組及其長度、結果數組

// 返回結果數組的長度

// （需要自行保證結果數組足夠大）

size_t getIntersection_optimized(array1, array1_len, array2, array2_len, result_array)

int* array1, * array2, * result_array;

size_t array1_len, array2_len;

{

size_t result_p = 0;

size_t i = 0;

// 使用標准庫的 qsort 比較方便

int* tmpArray = (int*)malloc(sizeof(int) * (array1_len + array2_len));

for (i = 0; i < array1_len; ++i) tmpArray[i] = array1[i];

for (i = 0; i < array2_len; ++i) tmpArray[array1_len + i] = array2[i];

qsort(tmpArray, array1_len + array2_len, sizeof(int), intAscendingComparor);

for (size_t i = 0; i < array1_len + array2_len - 1; ++i)

{

if (tmpArray[i] == tmpArray[i + 1])

{

result_array[result_p++] = tmpArray[i];

do {

++i;

} while (i < array1_len + array2_len - 1 && tmpArray[i] == tmpArray[i + 1]);

}

}

free(tmpArray); tmpArray = NULL;

return result_p;

}

// 自定義的一個簡單的輸出數組內容的函數

void printArray(int* array, size_t len)

{

for (size_t i = 0; i < len - 1; ++i)

{

printf("%d, ", array[i]);

}

printf("%d", array[len - 1]);

}

int main()

{

clock_t start, end;

int first_array[5] = { 1, 2, 3, 4, 5 };

int second_array[4] = { 4, 5, 6, 7 };

printf("數組1為：{ 1, 2, 3, 4, 5 }，數組2為：{ 4, 5, 6, 7 } ");

// 第一種方法

int result_array[10];

start = clock();

size_t result_array_len = getIntersection(first_array, 5, second_array, 4, result_array);

end = clock();

printf("交集為：{ ");

printArray(result_array, result_array_len);

printf(" }，使用時間：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

// 第二種方法

start = clock();

result_array_len = getIntersection_optimized(first_array, 5, second_array, 4, result_array);

end = clock();

printf("使用優化演算法求出的交集：{ ");

printArray(result_array, result_array_len);

printf(" }，使用時間：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

// 接下來用兩個比較大的數組，測試一下兩種方法的效率

printf(" 下面是測試，求一個包含 100000 個元素和一個包含 199999 個元素的數組的交集： ");

#define len1 100000

#define len2 199999

int* testArray1 = (int*)malloc(sizeof(int) * len1);

int* testArray2 = (int*)malloc(sizeof(int) * len2);

int* testArray = (int*)malloc(sizeof(int) * len1);

start = clock();

for (size_t i = 0; i < len1; ++i) testArray1[i] = i;

for (size_t i = 0; i < len2; ++i) testArray2[i] = i + 12345;

end = clock();

printf("初始化數組用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

start = clock();

result_array_len = getIntersection(testArray1, len1, testArray2, len2, testArray);

end = clock();

printf("第一種方法用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

start = clock();

result_array_len = getIntersection_optimized(testArray1, len1, testArray2, len2, testArray);

end = clock();

printf("第二種方法用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

return 0;

}

注釋應該說明得比較清楚了，這里就不贅言了。

下面分別是在 Windows 上 msvc 和 mingw 編譯並運行的結果：

mingw

『貳』 如何求兩個數組的交集

可以新建一個集合，遍歷一個數組，逐個判斷另一個數組是否包含這個元素，包含則list.add()，最後這個list中的元素，就是重疊的

『叄』 求兩個數組的交集演算法

數組求交集的方法
1.暴力搜索
2.利用HashMap
3.先排序再用兩個指針查找
4.點陣圖法
5.大文件求交集用分治法，組內用點陣圖法

『肆』 求助：兩個數組的交集

在php中求數組的交集，我們可以與PHP給我們提供的現成函數：array_intersect()，其用法格式為：

array array_intersect(array array1,array array2[,arrayN…])

根據上述的語法格式，我們來寫一個例子：

1 <?php
2 $fruit1 = array("Apple","Banana","Orange");
3 $fruit2 = array("Pear","Apple","Grape");
4 $fruit3 = array("Watermelon","Orange","Apple");
5 $intersection = array_intersect($fruit1, $fruit2, $fruit3);
6 print_r($intersection);
7 // 輸出結果：
8 // Array ( [0] => Apple )
9 ?>

本例子將返回在$fruit1數組中出現且在$fruit2和$fruit3中也出現的所有水果的名子。

使用array_intersect()函數時要注意：只有在兩個元素相等且具有相同的數據類型時，array_intersect()函數才會認
為它們是相同的，否則不能進行交集計算。array_intersect()函數返回一個保留了鍵的數組，只由第一個數組中出現的且在其它數組中都出現的
值組成。

若要求關聯數組的交集，請使用array_intersect_assoc()函數，給你個簡單的例子：

1 <?php
2 $fruit1 = array("red"=>"Apple","yellow"=>"Banana","orange"=>"Orange");
3 $fruit2 = array("yellow"=>"Pear","red"=>"Apple","purple"=>"Grape");
4 $fruit3 = array("green"=>"Watermelon","orange"=>"Orange","red"=>"Apple");
5 $intersection = array_intersect_assoc($fruit1, $fruit2, $fruit3);
6 print_r($intersection);
7 // 輸出：
8 // Array ( [red] => Apple )
9 ?>

array_intersect_assoc()函數語法格式如下：

array array_intersect_assoc(array array1,array array2[,arrayN…])

array_intersect_assoc()與array_intersect()基本相同，只不過他在比較中還考慮了數組的鍵。因此，只有在第一個數組中出現，且在所有其他輸入數組中也出現的鍵/值對才返回到結果數組中。

『伍』 如何快速取兩個二維數組中的交集

一維數組取交集是非常的簡單，直接用一個函數即可。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)
);

『陸』 怎樣對數組進行交集與並集運算

數組的並集
給定兩個數組：
int[] a = {1, 2, 3, 4, 5};
int[] b = {2, 3, 5, 6, 7};
輸出：
1,2,3,4,5,6,7
我的思路：
兩個數組的交集第一時間想到的肯定是最簡單的兩兩比較，如果相等就加進新數組，但是這樣做會造成時間的大量浪費，如果兩個長度各1W的數組，比較完的時間….不可想像。
然後馬上就想到Java的HashSet,重復不添加，所以把所有的數組遍歷進Set,再遍歷Set豈不是就完成了。
於是很容易實現了我的代碼：
int[] a = {1, 2, 3, 4, 5}; int[] b = {2, 3, 5, 6, 7};
HashSet<Integer> hashSet = new HashSet<>(); for (int aNum : a) {
hashSet.add(aNum);
} for (int bNum : b) {
hashSet.add(bNum);
}
Iterator<Integer> iterator = hashSet.iterator(); while(iterator.hasNext()){
System.out.print(iterator.next()+" ");
}

數組的交集
給定兩個數組：
int[] a = {1, 2, 3, 4, 5};
int[] b = {2, 3, 5, 6, 7};
輸出：
3,4,5
我的思路：與之前相同，強行跑遍歷的演算法肯定是不可取的，又想到了之前在一堆有重復數的數組中找出唯一一個沒有重復的演算法：
一是看到的最優解對自身進行^運算。
二是自己思考出的通過HashMap對每個數進行個數統計，如果為1則得出。
同理得出此處交集的運算規則，統計每一個數的出現次數，如果為2，則是交集。
以下為代碼實現：
int[] a = {1, 2, 3, 4, 5}; int[] b = {2, 3, 5, 6, 7};
HashMap<Integer, Integer> hashMap = new HashMap(16); for (int i = 0; i < a.length; i++) { if (hashMap.get(a[i]) != null) {
hashMap.put(a[i], hashMap.get(a[i]) + 1);
} else {
hashMap.put(a[i], 1);
}
} for (int i = 0; i < b.length; i++) { if (hashMap.get(b[i]) != null) {
hashMap.put(b[i], hashMap.get(b[i]) + 1);
} else {
hashMap.put(b[i], 1);
}
} for (int i : hashMap.keySet()) { if (hashMap.get(i).equals(2)) {
System.out.print(i+" ");
}
}
}

『柒』 有什麼好的演算法求兩個數組的交集

首先對較短的一個數組（設長度為a）建立平衡二叉搜索樹（需要alog2（a）的時間）。
然後對另一個數組（設長度為b）的每一個元素，在a的搜索樹中查找（需要blog2（a）的時間）。
所以總共需要alog2（a）＋blog2（a）的時間。
而2樓的演算法需要ab的時間。
當b>a>4時，
a>2log2(a)
log2(a)<a-log2(a)
log2(a)/(a-log2(a))<1
alog2(a)/(a-log2(a))<a
又b>a
alog2(a)/(a-log2(a))<b
alog2(a)<ab-blog2(a)
alog2(a)+blog2(a)<ab
所以b>a>4時我的演算法比2樓快。
當然，還有常數項的問題，上面的「快」只是漸進意義上的快。

『捌』 如何求兩個數組的交集

定義另外一個數組，做一個循環，把兩個數組的元素從下標為0的開始比較，又相等的就存到第三個數組中，一直到某一個數組的元素全部遍歷完以後。第三個數組中即為這兩個數組的交集。

『玖』 如何計算兩個有序整型數組的交集

例如，兩個含有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重復使用。

方法二：採用與方法一類似的方法，但是每次查找在前一次查找的基礎上進行，這樣可以大大縮小查找表的長度。

方法三：採用與方法二類似的方法，但是遍歷長度小的數組的方式有所不同，從數組頭部和尾部同時開始遍歷，這樣可以進一步縮小查找表的長度。

『拾』 如何取兩個已排序數組的交集

例如，兩個含有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();
}