学步园

这道题有问题，原以为交集是集合，集合是没有重复元素的。但是其实：

input:

3 -1

3 3 -1

output:

3

input:

3 3 -1

3 -1

output:

3

input:

3 3 -1

3 3 -1

output:

3 3

导致二分搜索不好用（请原谅我用的是数组），要额外一个数组保存次数。

我的是hash加二分查找

// UNSOVLED
/*
   3 -1
   3 3 -1

   3 3 -1
   3 -1

   3 3 -1
   3 3 -1
*/
#include <stdio.h>

#define debug	printf
#define MAX		65535

char flag[MAX+1];
int big[10001][2];
int main()
{
	freopen("in.txt", "r", stdin);
	int i=0, j=0;
	int n1, n2;
	int l=0, r=0, m;
	char* f = &flag[1];
	do{
		scanf("%d", &n1);
		if(n1 < MAX)
			f[n1]++;	// in case there're some same numbers
		else{
			big[i][1]++;
			big[i++][0] = n1;
		}
	}while(n1!=-1);
	do{
		scanf("%d", &n2);
		if(-1 == n2) break;
		if(n2 < MAX){// hash
			if(f[n2] > 0){
				if(0==j) printf("%d", n2);
				else printf(" %d", n2);
				f[n2]--;
				j++;
			}
		}
		else{// binary
			r=i-1;
			while(l <= r){
				m = (l+r)/2;
				if(big[m][0] == n2){
					if(big[m][1] == 0) break;
					if(0==j) printf("%d", n2);
					else printf(" %d", n2);
					big[m][0]--;
					j++;
					break;
				}
				else if(big[m][0] > n2)
					r = m-1;
				else
					l = m+1;
			}
			if(l>0) l--;	// in case big[l-1]==big[l]
		}
	}while(1);
	if(0==j) printf("NULL");

	return 0;
}

当然用链表或数组直接交互遍历最简便。