數組交集c語言

㈠ 編寫程序，實現兩個集合的交運算（用c語言）

#include<stdio.h>
#include<string.h>
intjiaoji(intA[],intB[],inta,intb)
{
	inti,j,t;
	t=a;
	for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(A[i]==B[j])
			{
				A[t]=B[j];
				t++;
			}
		}
		for(i=0;i<t-a;i++)
		{
		A[i]=A[a+i];
		}
		returnt-a;
}
intmain()
{
	intA[50],B[50],a,b,t;
	printf("請輸入A的元素個數：
");
	scanf("%d",&a);
	printf("請輸入A的元素：
");
	for(inti=0;i<a;i++)
		scanf("%d",&A[i]);
	printf("請輸入B的元素個數：
");
	scanf("%d",&b);
	printf("請輸入B的元素：
");
	for(inti=0;i<b;i++)
		scanf("%d",&B[i]);
	t=jiaoji(A,B,a,b);
	for(inti=0;i<t;i++)
		printf("%d",A[i]);
return0;
}

㈡ 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

㈢ 如何計算兩個有序整型數組的交集

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

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

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