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;
}