1. 哈希查找

时间 O(n) 空间 O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ComNum_Hash(int a[],int lenA,int b[],int lenB,int *comlst)
{
int hashTb[MAX_INT] = {0},i,j,k=0;

for(i = 0; i < lenA; i++)
hashTb[a[i]] = 1;

for(j = 0; j < lenB; j++)
{
if(hashTb[b[j]] == 1)
comlst[k++] = b[j];
}

return k;
}

Java 直接调用

1
2
3
4
5
6
7
8
9
10
11
List<String> list1 = new ArrayList<String>();
List<String> list2 = new ArrayList<String>();
list1.add("g");
list1.add("s");
list1.add("a");
list1.add("f");
list2.add("g");
list2.add("c");
list2.add("b");
list2.add("a");
list1.retainAll(list2);

2. 二路归并

时间O(nlog2n) 空间O(n)

1
2
3
4
5
6
7
8
9
10
11
12
int count()
{
total=i=j=0;
while(i<n && j<n)
{
if(a[i]<b[j]) i++;
else if(a[i]>b[j])j++
else
total++;
}
return total;
}