求两个大数集合的交集问题.

cyberhero 2009-08-10 10:50:01
我有N个大数组, 大小为变长,求这N个数组的交集,大家有过这样的算法吗?
...全文
2514 30 打赏 收藏 转发到动态 举报
写回复
用AI写文章
30 条回复
切换为时间正序
请发表友善的回复…
发表回复
liuzenghui2007 2011-06-02
  • 打赏
  • 举报
 回复
我那天做了这道题目，一个公司的 笔试题
我当时这样想的，
1 先对每个集合排序，得到所有结合的最大值和最小值（最好去掉重复值）
2 求所有集合的最小值中的最大值a，和所有集合的最大值中的最小值b，交集一定事[a,b]的子集
3 在[a,b]中扫描每一个整数，如果该整数在所有集合中存在，则记录并打印输出
boYwell 2010-10-21
  • 打赏
  • 举报
 回复
mark up ~~~~~~~~~~
fallening 2009-08-21
  • 打赏
  • 举报
 回复
晕，回复发错了帖子
fallening 2009-08-21
  • 打赏
  • 举报
 回复
设这两个数组分别为A[N],B[M] (N<=M)

1)对A[N]排序 －－ 时间复杂度NlgN;
2)对B[M]中的每一个元素，在已经排序好的A[N]中二分查找 －－时间复杂度 MlgN

综上，时间复杂度为 (M+N)lgN
chogimoga 2009-08-21
  • 打赏
  • 举报
 回复
容斥原理
cyberhero 2009-08-21
  • 打赏
  • 举报
 回复
[Quote=引用 2 楼 diannaomingong 的回复:]
用STL的set吧
有交集运算

不过如果n个集合逐一合并,比较耗时


[/Quote]

不使用STL，纯C
firePhoenix1981 2009-08-13
  • 打赏
  • 举报
 回复
我也提一个方法试试
1）对某个数组构造trie树，每个节点设置一个标记域ID
2）第二的数组在此trie树中进行查找，将找到的ID+1
3）其他的数组按照第二步的方法操作
4）最后ID为N-1的节点即为N个数组的交集

可以将每次没有匹配到的节点删除，这样就可以大大减少后续的匹配次数
tanwan 2009-08-13
  • 打赏
  • 举报
 回复
2个数组排序之后,先在第一个数组中找出满足要求的头(既当头)然后在拿个变量累加直到不满足条件为止,然后这些就是a和b数组的交集了吧!!!
linren 2009-08-13
  • 打赏
  • 举报
 回复
【程序】
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <windows.h>

/**只用修改这里*******************************/

#define ASIZE 10

int a[ASIZE]={43,6,14,8,4,223,7,109,343,33};



#define BSIZE 20

int b[BSIZE]={-176, 7, 437, 33, 164, -33, -393, 285,

-279, -290, 217, -325, -316, 51, -377, -195,

318, -141, -277, -18};



#define CSIZE 25

int c[CSIZE]={47,-439, -327, 294, 316, -167, 312, -60, -112,

-35, 211, -180, 131, -245, -207, -284, 33,

-271, 486, -184, 120, -465, 179, 7, -156};

/*******************************只用修改这里**/



struct node{

	int *a;

	int len;

};



struct list{

	struct node* book;

	int len,size;

};



void init_list(struct list *ls,int size){

	ls->book=(struct node*)malloc(sizeof(struct node)*size);

	ls->size=size;

	ls->len=0;

}



void del_list(struct list *ls){

	free(ls->book);

}



void insert_to_list(struct list *ls,int *a,int len){

	if(ls->len==ls->size){

		printf("can not insert information, because the list is full...\n");return;

	}

	ls->book[ls->len].a=a;

	ls->book[ls->len].len=len;

	ls->len++;

}



int compar(const void *a,const void *b){

	int *x=(int*)a;

	int *y=(int*)b;

	if(*x>*y) return 1;

	if(*x==*y) return 0;

	return -1;

}



void fun(struct list *ls){

	int i,j,k,t,t2,x,c;

	int *ta,*pb,*pe;

	int **p;

	int flg=1;



	k=ls->len;



	/* 数组排序 */

	for(i=0;i<k;i++){

		qsort(ls->book[i].a,ls->book[i].len,sizeof(int),compar);

	}



	/* 生成保存结果缓冲区 */

	t2=-1;

	for(i=0;i<k;i++){

		if(t2<ls->book[i].len||t2==-1) t2=ls->book[i].len;

	}

	ta=(int*)malloc(sizeof(int)*t2);



	/* 准备 */

	p=(int**)malloc(sizeof(int*)*k);

	pb=(int*)malloc(sizeof(int)*k);

	pe=(int*)malloc(sizeof(int)*k);

	for(i=0;i<k;i++){

		p[i]=ls->book[i].a;

		pe[i]=ls->book[i].len;

	}

	memset(pb,0,sizeof(int)*k);



	/* 求交集 */

	t=0;

	//选一个最大的数并记录位置

	x=p[0][pb[0]];j=0;

	for(i=1;i<k;i++){

		if(p[i][pb[i]]>x){

			j=i;x=p[i][pb[i]];

		}

		if(pb[i]==pe[i]) flg=0;

	}

	while(flg){

		c=1;

		for(i=0;i<k;i++){

			if(i==j) continue;

			while(pb[i]<pe[i]){

				if(p[i][pb[i]]>=x) break;

				pb[i]++;

			}

			if(p[i][pb[i]]==x) c++;

		}

		//记录一个交集元素

		if(c==k){

			ta[t++]=x;

			for(i=0;i<k;i++) pb[i]++;

		}

		//选一个最大的数并记录位置

		x=p[0][pb[0]];j=0;

		for(i=1;i<k;i++){

			if(p[i][pb[i]]>x){

				j=i;x=p[i][pb[i]];

			}

			if(pb[i]==pe[i]) flg=0;

		}

	}



	/* 打印结果 */

	if(t==0) printf("φ\n");

	else{

		for(i=0;i<t;i++) printf("%d, ",ta[i]);

		printf("\n");

	}



	free(ta);free(p);free(pe);

}



int main(){

	/* 创建一个保存数组信息的结构体 */

	struct list ls;

	init_list(&ls,4);



	/* 将数组信息填写进结构体内 */

	insert_to_list(&ls,c,CSIZE);

	insert_to_list(&ls,a,ASIZE);

	insert_to_list(&ls,b,BSIZE);



	/* 求多个数组的交集 */

	fun(&ls);



	del_list(&ls);return 0;

}

【运行结果】
7, 33,
Press any key to continue

【说明】
以上程序采用了14楼的思路

【性能测试】
对13楼的程序和本楼的程序进行性能测试
测试用例是：
在关闭打印结果的情况下调用1000000次fun()……

13楼的测试结果为：
use time: 9922.637095 ms
Press any key to continue

本楼的测试结果为：
use time: 12167.887818 ms
Press any key to continue

非常接近……
linren 2009-08-13
  • 打赏
  • 举报
 回复
[Quote=引用 14 楼 todaylxp 的回复:]
1.先各自排序，这个是毫无疑问的
2.然后像搜索引擎的合并算法，指针指向各个数组，如果遍历各个数组当前值
如果都相等，就是一个交集元素，如不相等，以最大值的那个数组为基准值，其他数组都往后移动指针
直至值大于等于基准值
3.重复之
[/Quote]
恩
这个办法好……
linren 2009-08-13
  • 打赏
  • 举报
 回复
（上接13楼）
13楼的程序有个地方写错了……

/* 打印结果 */
if(flg==0){
for(i=0;i<t2;i++) printf("%d, ",ta[i]);printf("\n");
}else{
for(i=0;i<t2;i++) printf("%d, ",tb[i]);printf("\n");
}

else里的应该是tb不是ta……（晕）
todaylxp 2009-08-13
  • 打赏
  • 举报
 回复
1.先各自排序，这个是毫无疑问的
2.然后像搜索引擎的合并算法，指针指向各个数组，如果遍历各个数组当前值
如果都相等，就是一个交集元素，如不相等，以最大值的那个数组为基准值，其他数组都往后移动指针
直至值大于等于基准值
3.重复之
linren 2009-08-13
  • 打赏
  • 举报
 回复
【程序】
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/**只用修改这里*******************************/

#define ASIZE 10

int a[ASIZE]={43,6,14,8,4,223,7,109,343,33};



#define BSIZE 20

int b[BSIZE]={-176, 412, 437, 33, 164, -33, -393, 285,

-279, -290, 217, -325, -316, 51, -377, -195,

318, -141, -277, -18};



#define CSIZE 25

int c[CSIZE]={47,-439, -327, 294, 316, -167, 312, -60, -112,

-35, 211, -180, 131, -245, -207, -284, 33,

-271, 486, -184, 120, -465, 179, 461, -156};

/*******************************只用修改这里**/



struct node{

	int *a;

	int len;

};



struct list{

	struct node* book;

	int len,size;

};



void init_list(struct list *ls,int size){

	ls->book=(struct node*)malloc(sizeof(struct node)*size);

	ls->size=size;

	ls->len=0;

}



void del_list(struct list *ls){

	free(ls->book);

}



void insert_to_list(struct list *ls,int *a,int len){

	if(ls->len==ls->size){

		printf("can not insert information, because the list is full...\n");return;

	}

	ls->book[ls->len].a=a;

	ls->book[ls->len].len=len;

	ls->len++;

}



int compar(const void *a,const void *b){

	int *x=(int*)a;

	int *y=(int*)b;

	if(*x>*y) return 1;

	if(*x==*y) return 0;

	return -1;

}

int compar2(const void *a,const void *b){

	struct node *x=(struct node*)a;

	struct node *y=(struct node*)b;

	if(x->len>y->len) return 1;

	if(x->len==y->len) return 0;

	return -1;

}

void fun(struct list *ls){

	int i,j,k,t,t2;

	char flg;

	int *ta,*tb;

	/* 数组排序 */

	for(i=0;i<ls->len;i++){

		qsort(ls->book[i].a,ls->book[i].len,sizeof(int),compar);

	}

	/* 数组长度排序 */

	for(i=0;i<ls->len;i++){

		qsort(ls->book,ls->len,sizeof(struct node),compar2);

	}

	

	ta=(int*)malloc(sizeof(int)*ls->book[0].len);

	tb=(int*)malloc(sizeof(int)*ls->book[0].len);

	t2=ls->book[0].len;

	memcpy(ta,ls->book[0].a,sizeof(int)*t2);



	/* 求交集 */

	flg=0;

	for(i=1;i<ls->len;i++){

		t=0;j=0;k=0;

		while(j<t2&&k<ls->book[i].len){

			if(flg==0){

				if(ta[j]==ls->book[i].a[k]){

					tb[t]=ta[j];j++;k++;t++;

				}else if(ta[j]<ls->book[i].a[k]) j++;

				else k++;

			}else{

				if(tb[j]==ls->book[i].a[k]){

					ta[t++]=tb[j];j++;k++;

				}else if(tb[j]<ls->book[i].a[k]) j++;

				else k++;

			}

		}

		if(t==0){

			printf("φ\n");free(ta);free(tb);return;

		}

		t2=t;

		if(flg==0) flg=1;

		else flg=0;

	}

	

	/* 打印结果 */

	if(flg==0){

		for(i=0;i<t2;i++) printf("%d, ",ta[i]);printf("\n");

	}else{

		for(i=0;i<t2;i++) printf("%d, ",ta[i]);printf("\n");

	}

	

	free(ta);free(tb);

}



int main(){

	/* 创建一个保存数组信息的结构体 */

	struct list ls;

	init_list(&ls,4);



	/* 将数组信息填写进结构体内 */

	insert_to_list(&ls,c,CSIZE);

	insert_to_list(&ls,a,ASIZE);

	insert_to_list(&ls,b,BSIZE);



	/* 求多个数组的交集 */

	fun(&ls);



	del_list(&ls);return 0;

}

【运行结果】
33,
Press any key to continue
diannaomingong 2009-08-13
  • 打赏
  • 举报
 回复
直接用set不就排好序并且提供合并了,为何要自己发明轮子
henry11 2009-08-13
  • 打赏
  • 举报
 回复
xuexi
绿色夹克衫 2009-08-13
  • 打赏
  • 举报
 回复
改正一下，最后不用遍历Hash表，只需要在读入最后1个集合的时候，判断计数+1 = 集合个数的元素，直接输出就行了！
绿色夹克衫 2009-08-13
  • 打赏
  • 举报
 回复
直接用hash不可以么？不排序O(n)就行，建立1个Hash表，读入第一个集合，
将集合元素逐一放入Hash表，并将计数设为1，然后逐个读入后面的集合，每读一个集合，集合计数+1

每读一个集合元素，作如下判断：

读到的元素如果不在Hash表中，则忽略，如果在集合中，则判断集合里面的计数+1是否=当前集合的计数，
如果=，则计数+1，如果小于，则将该元素从集合中删除。

最后遍历一下Hash表，输出计数=集合个数的元素。

鼠 2009-08-13
  • 打赏
  • 举报
 回复
效率要求不高的话就直接用 STL 吧，简洁。


#include <algorithm>

#include <iostream>

using std::set_intersection;

using std::sort;

using std::cout;

using std::endl;

#define ASIZE 10

int a[ASIZE]={43,6,14,8,4,223,7,109,343,33};



#define BSIZE 20

int b[BSIZE]={-176, 7, 437, 33, 164, -33, -393, 285,

-279, -290, 217, -325, -316, 51, -377, -195,

318, -141, -277, -18};



#define CSIZE 25

int c[CSIZE]={47,-439, -327, 294, 316, -167, 312, -60, -112,

-35, 211, -180, 131, -245, -207, -284, 33,

-271, 486, -184, 120, -465, 179, 7, -156};



int result[CSIZE];



void sortIt()

{

    sort(a, a+ASIZE);

    sort(b, b+BSIZE);

    sort(c, c+CSIZE);

}



int merge()

{

    int *pBegin=result, *pEnd=result+CSIZE;

    pEnd=set_intersection(a, a+ASIZE, b, b+BSIZE, pBegin);

    pEnd=set_intersection(pBegin, pEnd, c, c+CSIZE, pBegin);  //这样不知道安全不安全

    return pEnd-pBegin;

}



int main()

{

    sortIt();

    int resSize = merge();

    for(int i=0; i<resSize; ++i)

    {

        cout<<result[i]<<' ';

    }

    cout<<endl;

}

输出：
7 33
Tue 2009-08-13
  • 打赏
  • 举报
 回复
STL集合支持交集，差集，合集，直接用，很方便的。
nathan_sz 2009-08-13
  • 打赏
  • 举报
 回复
N个数组中所有元素排好序，顺便计算各个元素的个数，哪个元素个数等于N，这个就是交集
加载更多回复（10）
2个大数组求交集的情况
3万多个元素的数组和2万多的数组也会很快求出交集
两个数组的交集
两个数组的交集一、题目二、思想和代码1，先对数组进行排序2，使用map解决 一、题目 给定两个数组，编写一个函数来计算它们的交集。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2: 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9] 说明： （1）输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。 （2）我们可以不考虑输出结果的顺序。 二、思想和代码 1，先对数组进
两个数组的交集(C++)
返回 它们的交集。输出结果中的每个元素一定是。
【C++】两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 思路： std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并
java计算两个数组的交集_回顾面试题：计算两个数组交集
背景工作多年，语言经历过C#,JAVA。但是做过的项目大多以业务系统为主，曾经做过一些基础架构的工作，但算法一直在工作中应用的比较少，导致多年之后基本都忘记完了。上一次面试过程中就有一个算法题，我能做对，但是感觉不是最优方案就放弃了。最近想想做为一个程序员，算法还是有必要再补习补习。案例有两个数组，int[] arrayA=new int[]{1,3,1.....},int[] arrayB=ne...
数据结构与算法

33,008

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章