演算法取交集
先排序兩個先行表，然後去除重復項。
從一個表(a)第一項開始，為關鍵字掃描另一個表(b)，找一個與其相等的，如果找到，那麼在b表之前的項也不會是a表中的項了，然後從a表下一項作關鍵字，從b表被匹配的元素的下一項開始繼續搜索，如果沒有找到與a中第一項相等的，到遇到比該項大的項時，便從a中下一項開始，重復以上步驟。
排序就不說了，好多種，冒泡，快排，插入，二分插入都行。去除重復項，可以用以下演算法
void StripRepeatElement(int Array[],int Arraylen)
{
int Count = 0;//重復計數器
int i;
for(i = 0;i < ArrayLen;i++)
{
if(Array[i] == Array[i + 1])
{
Count++;
}
else
{
Array[i - Count] = Array[i];
}
}
}
復雜度為O(n)
以下為求交集的演算法，假設兩個表都已經排過序和剔出重復項了
void GetIntersection(int A[],int Alen,int B[],int Blen)
{
int i = 0,j = 0;
while(i < Alen)
{
while(j < Blen)
{
if(A[i] == B[j])
{
//交集
printf(" %d ",A[i]);
j++;
break;
}
else if(A[i] < B[j])
{
//從A的下一項開始匹配
break;
}
else
{
//比較B的下一項
j++;
}
}
i++;
}
}
復雜度也為O(n)
2. 有什麼好的演算法求兩個數組的交集
首先對較短的一個數組（設長度為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樓快。
當然，還有常數項的問題，上面的「快」只是漸進意義上的快。
3. 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
4. 求兩個集合的交集，用c++語言寫
#include<stdio.h>
double P[n1],Q[n2]; //R=P∩Q
double R[];
double TEMP;
for(i=0;i<n1;i++)
{for(j=0;j<n2;j++)
if(P[i]==Q[j])
{
TEMP=P[i];
R[m]=TEMP;
m++;
}
}
5. 求兩個集合交集的演算法
我這里有一個很強的，是以前的作業，功能有很多！
有問題來找小斌
QQ：504449327
#define
TRUE
1
#define
FALSE
0
#define
OK
1
#define
ERROR
0
#define
INFEASIBLE
-1
#define
OVERFLOW
-2
typedef
int
Status;
typedef
char
ElemType;
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<conio.h>
typedef
struct
NodeType
{
ElemType
data;
struct
NodeType
*next;
}
NodeType,*LinkType;
typedef
struct
{
LinkType
head,tail;
int
size;
}OrderedList;
ElemType
a[100]="magazine";
ElemType
b[100]="paper";
OrderedList
L1,L2,L3;
Status
MakeNode(LinkType
&p,ElemType
e)/*函數功能，創建一個結點，用p指向它，並把e的值賦給date*/
{
p=(LinkType)malloc(sizeof(NodeType));
if(!p)
return
FALSE;
p->data=e;
p->next=NULL;
return
TRUE;
}
Status
InitList(OrderedList
&L)
/*函數功能，建立空棧*/
{
if(MakeNode(L.head,'
'))
{
L.tail=L.head;
L.size=0;
return
TRUE;
}
else
{
L.head=NULL;
return
FALSE;
}
}
Status
LocateElem(OrderedList
L,
ElemType
e,
LinkType
&p)
{
NodeType
*pre;
if(L.head)
/*棧建立成功*/
{
pre=L.head;
p=pre->next;
while(p
&&
p->data<e)
/*第二個結點中的data比e小，就讓p和pre指向下一個結點*/
{
pre=p;
p=p->next;
}
if(p
&&
p->data==e)/*找到和e相等的date，p指向這個結點*/
{
return
TRUE;
}
else
/*如果找不到，p指向剛好比e小的結點*/
{
p=pre;
return
FALSE;
}
}
else
return
FALSE;
}
void
InsertAfter(OrderedList
L,
LinkType
q,
LinkType
s)
/*在結點q之後插入s結點*/
{
if(L.head
&&
q
&&
s)
{
s->next=q->next;
q->next=s;
if(L.tail==q)
L.tail=s;
L.size++;
}
}
void
CreateSet(OrderedList
&T,
char
*s)/*將s中的元素按從小到大的順序插入到T控制的鏈表中*/
{
unsigned
i;
LinkType
p
,q;
if(InitList(T))
/*建立一個空棧*/
{
for(i=0;i<=strlen(s);i++)
{
if(s[i]>='a'
&&
s[i]<='z'
&&
!LocateElem(T,s[i],p))
{
if(MakeNode(q,s[i]))
{
InsertAfter(T,p,q);
}
}
}
}
}
Status
Print(LinkType
p)/*輸出一個鏈表*/
{
if(p)
{
printf("%c",p->data);
return
TRUE;
}
else
return
FALSE;
}
void
ListTraverse(LinkType
p,
Status
(*visit)(
LinkType
))
{
printf("%c",'\t');
while(p)
{
visit(p);
//這句看不懂
p=p->next;
}
printf("%c",'\n');
}
void
Append(OrderedList
&L,LinkType
s)
{
if(L.head
&&
s)
{
if(L.tail!=L.head)
L.tail->next=s;
else
L.head->next=s;
L.tail=s;
L.size++;
}
}
void
Union(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(InitList(T))
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<=p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
if(p1->data==p2->data)
p2=p2->next;
p1=p1->next;
}
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
while(p2)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
}
void
Intersection(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<p2->data)
p1=p1->next;
else
if(p1->data>p2->data)
p2=p2->next;
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
p1=p1->next;
}
}
}
}
void
Difference(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
else
if(p1->data>p2->data)
p2=p2->next;
else
{
p1=p1->next;
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
}
}
void
ReadCommand(char
&cmd)
{
printf("\n
------------------------------------------------------------------------\n");
printf("\n\t\t\t\t操
作
提
示");
printf("\n
------------------------------------------------------------------------\n");
printf("\tMakeSet1------1\t\t\t\tMakeSet2--------2\n\tUnion---------u\t\t\t\tIntersection----i\n\tDifference----d\t\t\t\tQuit------------q\n\tDisplay-------y");
do{
printf("\n\n\t請選擇操作：");
cmd=getch();
printf("\n--------------------------------------------------------------------------\n");
}while(cmd!='1'
&&
cmd!='2'
&&
cmd!='u'
&&
cmd!='i'
&&
cmd!='d'
&&
cmd!='q'
&&
cmd!='y');
}
void
Interpret(char
&cmd)
{
system("cls");
switch(cmd)
{
case
'1':
printf("\n\t請輸入字元串：");
gets(a);
printf("\t原始字元串:");
printf("\t%s\n",a);
CreateSet(L1,
a);
printf("\t構建的集合:");
ListTraverse(L1.head->next,Print);
break;
case
'2':
printf("\n\t請輸入字元串：");
gets(b);
printf("\t原始字元串:");
printf("\t%s\n",b);
CreateSet(L2,
b);
printf("\t構建的集合:");
ListTraverse(L2.head->next,Print);
break;
case
'u':
CreateSet(L1,
a);
CreateSet(L2,
b);
Union(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t並集:");
ListTraverse(L3.head->next,Print);
break;
case
'i':
CreateSet(L1,
a);
CreateSet(L2,
b);
Intersection(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t交集:");
ListTraverse(L3.head->next,Print);
break;
case
'd':
CreateSet(L1,
a);
CreateSet(L2,
b);
Difference(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
case
'y':
printf("\n\t原始字元串:\n");
printf("\t\t%s\n\t\t%s\n",a,b);
CreateSet(L1,
a);
CreateSet(L2,
b);
printf("\t由字元串構建的集合:\n");
printf("\t");
ListTraverse(L1.head->next,Print);
printf("\t");
ListTraverse(L2.head->next,Print);
Union(L3,L1,L2);
printf("\t並集:");
ListTraverse(L3.head->next,Print);
Intersection(L3,L1,L2);
printf("\t交集:");
ListTraverse(L3.head->next,Print);
Difference(L3,L1,L2);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
}
}
void
main()
{
char
cmd;
do
{
ReadCommand(cmd);
Interpret(cmd);
}while(cmd!='q');
}
6. python 多個字元串交集演算法
如果原數據是唯一的，就把每一個元素，添加到一個字典中
最終獲得類似{"A1":5,"A3":2,"D1":5,"D3":10}的字典，也就是記錄每一個元素出現的次數，如果是10個元組的交集，那麼次數=10。
7. 如何寫一個c語言程序求兩個集合的交集
定義兩個數組存放這兩個集合，再定義一個數組存放它們的集合，用類似冒泡排序的演算法，遍歷數組1中的第一個元素和數組2中每一個元素，若有相同的，則把這個元素放入第三個數組，繼續遍歷，知道數組1遍歷完所有元素，那數組3中的元素，即為兩個數組(集合)的交集。