首页 > 试题广场 >

A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

[问答题]
A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
添加回答
推荐
REDStone头像 REDStone
如果是有序的用二路归并求交集
如果是无序的可以用map或hash
发表于 2014-11-03 16:54:53 回复(1)
Hei$enberg头像 Hei$enberg 
#include <iostream>
#include <vector> 
#include <algorithm> 
using namespace std; 
vector<int> getIntersection(vector<int> &A, vector<int> &B) { 
    sort(A.begin(), A.end()); 
    sort(B.begin(), B.end()); 
    vector<int> result; 
    int i = 0, j = 0; 
    while(i < A.size() && j < B.size()) { 
        if(A[i] == B[j]) { 
            int t = A[i]; 
            result.push_back(t); 
            while(i < A.size() && A[i] == t) i++; 
            while(j < B.size() && B[j] == t) j++; 
        } 
        else if(A[i] < B[j]) { i++; } 
        else if(A[i] > B[j]) { j++; }
    } 
    return result; 
}

发表于 2015-09-04 22:20:33 回复(0)
duang头像 duang
直接用并查集就可以求解了呀，效率是O(n):
void getCommon(int a[], int b[], int lengthA, int lengthB){
 int i,visit[MAX],mark[MAX]; //初始化标记数组mark和访问数组visit
 memset(visit,0,sizeof(visit));
 memset(mark,0,sizeof(mark)):
 for(i=0;i<lengthA;i++){
  mark[a[i]]=1;  //当某个数在A集合中出现过，则用mark来标记
 }
 for(i=0;i<lenghtB;i++){
  int t = b[i];
  if(mark[t]==1&&!visit){   //当某数在B中出现，此时mark对应的标记为1，说明其在B集合中也出现，并且只输出一次
     visit[t]=1;   //只输出一次，用visit来控制
     printf("%d",t);
  }

 }
 return ;
}
发表于 2015-04-13 19:57:47 回复(4)
雷天琪头像 雷天琪
这个题提到了高效，可以理解为时间上的高效，和空间上的高效。
对于A，B两个数组，如果是亿级别的数量，或者更高，则要考虑空间的高效，此时可以用BitMap来存储，比如：
A：001011010101011100000010...
B：010101101100010110101110... 
然后用A&B，再求出结果中1的个数即可。这样既保证了空间高效，也保证了时间高效。

发表于 2015-09-03 07:05:06 回复(10)
Henson.头像 Henson.
参考答案：
如果是有序的用二路归并求交集
如果是无序的可以用map或hash
发表于 2018-09-18 11:35:01 回复(0)
指上弹兵赵小括头像 指上弹兵赵小括
先使用位图存储A，每bit可存储一个整数(将bit位从0变为1)。然后遍历B，若bit位为1，则输出；时间复杂度是O(m+n)，空间复杂度也不大；
发表于 2015-09-03 10:46:59 回复(1)
Once头像 Once
一个哈希记录小集合,遍历大的集合查找是否存在
发表于 2014-10-25 00:26:03 回复(0)
jerries头像 jerries
我举一个例子：
假设某个网站有200W用户，一个用户可以关注多个人，现在要以最快的速度和最省空间的办法来获取当前用户关注的人的动态，排序规则是时间倒序的方式...谁有办法解出来？
发表于 2018-01-10 18:04:26 回复(0)
萌萌哒天团头像 萌萌哒天团
哔哔哔哔哔
发表于 2017-11-25 09:52:01 回复(0)
黄小斜头像 黄小斜
hash
发表于 2017-04-03 16:37:27 回复(0)
幻影迷风头像 幻影迷风
KMP
发表于 2015-09-03 22:06:03 回复(3)
寻#头像 寻#
void printintersection(int A[], int n, int B[], int m)
{
//求两个整数集合A（长度为n）和B（长度为m）的交集
//利用set中元素的唯一性，multiset中元素的可重复性
if (A == NULL || B == NULL || n < 0 || m < 0)
{
return;
}
//去掉数组中的重复元素
set<int> setA;
for (size_t i = 0; i < n; i++)
{
setA.insert(A[i]);
}
set<int> setB;
for (int i = 0; i < m; i++)
{
setB.insert(B[i]);
}
//统计交集
multiset<int> mtset;
for (auto i : setA)
{
mtset.insert(i);
}
for (auto i : setB)
{
mtset.insert(i);
}

set<int> intersection;
for (auto i:mtset)
{
if (mtset.count(i) > 1)
{
intersection.insert(i);
}
}

//print
for (auto i : intersection)
{
cout << i << ends;
}
cout << endl;
}
发表于 2015-09-01 16:50:39 回复(1)
CodeSheep头像 CodeSheep 
vector<int> findIntersection( vector<int>& arr1, vector<int>& arr2 ){

	int m = arr1.size();
	int n = arr2.size();
	
	set<int> iset;
	
	for( int i=0; i<m; ++i )
		iset.insert( arr1[i] );
		
	vector<int> res;
	
	for( int i=0; i<n; ++i )
		if( iset.count( arr2[i] ) != 0 )
			res.push_back( arr2[i] );
	
	return res;
}

发表于 2015-08-29 17:11:52 回复(0)
远方的樱花头像 远方的樱花
<div> #include &lt;stdio.h&gt; </div> <div> <br /> </div> <div> void Union(int *a, int *b, int n, int m) </div> <div> { </div> <div> <span> </span>int c[20] = {0}; </div> <div> <span> </span>for(int i=0; i&lt;n; i++) </div> <div> <span> </span>{ </div> <div> <span> </span>c[a[i]]++; </div> <div> <span> </span>} </div> <div> <span> </span>for(i=0; i&lt;m; i++) </div> <div> <span> </span>{ </div> <div> <span> </span>c[b[i]]++; </div> <div> <span> </span>} </div> <div> <span> </span>for(i=0; i&lt;20; i++) </div> <div> <span> </span>{ </div> <div> <span> </span>if(c[i] &gt;= 2) </div> <div> <span> </span>printf("%d ", i); </div> <div> <span> </span>} </div> <div> <span> </span>printf("\n"); </div> <div> } </div> <div> <br /> </div> <div> int main() </div> <div> { </div> <div> <span> </span>int a[] = {1,2,3,4,5,6}; </div> <div> <span> </span>int b[] = {0,2,3,4,6,8,10}; </div> <div> <span> </span>int n = sizeof(a)/sizeof(a[0]); </div> <div> <span> </span>int m = sizeof(b)/sizeof(b[0]); </div> <div> <span> </span>Union(a,b,n,m); </div> <div> <span> </span>return 0; </div> <div> } </div>
发表于 2015-08-29 17:08:22 回复(0)
sundial头像 sundial
<?php
$arr1 = [1,2,3,4,5,6,7,8,9];
$arr2 = [0,3,5,7,10,11,12];
for($i=0;$i<count($arr1);$i++){
if(in_array($arr1[$i],$arr2)) echo $arr1[$i];
}
看。php多简单。。。
发表于 2015-08-29 16:49:48 回复(0)
逍遥界头像 逍遥界 
#include<iostream>
using namespace std;
/*
1)先使用快速排序，使得两个数组有序；
2)然后利用二分查找的方法，在数组B中查找；
3)其中，注意在数组B中，使用二分查找的起点，是根据上次查找的结果开确定的；这样可以进一步提高速度；
*/
int Sort(int array[],int low,int high)
{
	int temp=array[low];
	int pos=low;
	while(low<high)
	{
		while(array[high]>temp && high>low)high--;
		if(high>low)array[low]=array[high];
		while(array[low]<temp && high>low)low++;
		if(low<high)array[high]=array[low];
	}
	array[low]=temp;
	return low;
}
void QuickSort(int array[],int low,int high,int len)
{
    if(low<high)
	{
		int mid=Sort(array,low,high);
		QuickSort(array,low,mid-1,len);
		QuickSort(array,mid+1,high,len);
	}
}

int BinarySearch(int array[],int len,int start,int key)
{
	int pos=-1;
	int low=start;
	int high=len-1;
    int mid=0;
    while(low<=high)
	{
		mid=(low+high)/2;
		if(key>array[mid])low=mid+1;
		else if(key<array[mid])high=mid-1;
		else if(key==array[mid]) {pos=mid;break;}
	}
	return pos;
}
void Output(int array_A[],int array_B[],int len_A,int len_B)
{
	QuickSort(array_A,0,len_A-1,len_A);
    QuickSort(array_B,0,len_B-1,len_B);
	int i=0,j=0,current=0;//current 记录当前查找的位置；
	int*array_C =new int [len_A];
	int count=0;
	for(i=0;i<len_A;i++)
	{
		j=BinarySearch(array_B,len_B,current,array_A[i]);
		if(j==-1){continue;}
		else{
			array_C[count]=array_A[i];
			count++;
			current=j+1;
		}
	}
	if(array_C!=NULL)
	{
		for(i=0;i<count;i++)
		{
			cout<<array_C[i]<<" ";
		}
		cout<<endl;
	}
	delete []array_C;
	array_C=NULL;
}

int main()
{
	int array_A[10]={5,1,7,3,9,0,45,8,12,11};
	int array_B[10]={15,1,17,3,23,0,45,33,12,11};
	int len_A=10;
	int len_B=10;
    Output(array_A,array_B,len_A,len_B);
	return 0;
}


发表于 2015-08-26 19:21:12 回复(1)
小小娃爱吃甜食头像 小小娃爱吃甜食
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int be_count(int a[],int b[],int c[],int n1,int n2)
{
if(n1==0||n2==0)
return 0;
int res[125]={0},m=0;
for(int i=0;i<n1;i++)
{
res[a[i]]++;
}
for(int j=0;j<n2;j++)
{
if(res[b[j]]>0)
c[m++]=b[j];
}
return m;
}
int main()
{
int a[6]={2,7,8,9,0,4};
int b[6]={3,10,0,7,9,1};
int c[6];
int m=be_count(a,b,c,6,6);
for(int i=0;i<m;i++)
cout<<c[i]<<" ";
cout<<endl;
return 0;

}
发表于 2015-08-25 17:41:20 回复(0)
CloudCastle头像 CloudCastle
如果数据合适可以使用位图或者hash_map，时间复杂度均为 O(n)
发表于 2015-08-04 16:16:25 回复(0)
ABCD头像 ABCD 
int[] Same(int a1[],int a2[]){
    int len1=sizeof(a1)/sizeof(int);
    int len2=sizeof(a2)/sizeof(int);
    int len=len1<len2?len1:len2;
    int a3[len];
    int k=0;
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++){
            if(a1[i]==a2[j]){
                a3[k]=a1[i];
                k++;
            }
        }
    }
    return a3;
}

发表于 2015-06-26 09:26:45 回复(0)
shiawang头像 shiawang
既然是集合，类似于set，就假设集合整数是不重复的。
方法一：
数字不大。hash。或者hash加链式结构
方法二：
A进行排序，归并，堆，快排等都行，B进行二分查找。

发表于 2015-04-08 14:10:17 回复(0)
徐度灿头像 徐度灿
  1. #include <stdio.h>   
  2. #include <stdlib.h>   
  3. #define M 8   
  4. #define N 5   
  5. int  cmp( const   void  *a,  const   void  *b)  
  6. {  
  7.     int  *x = ( int  *)a;  
  8.     int  *y = ( int  *)b;  
  9.     return  (*x) - (*y);  
  10. }  
  11.   
  12. int  main( void )  
  13. {  
  14.     int  A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};  
  15.     int  B[] = {39 ,8 , 10, 6, -1};  
  16.     //对数组A和数组B进行快排   
  17.     qsort(A, M, sizeof ( int ), cmp);  
  18.     qsort(B, N, sizeof ( int ), cmp);  
  19.     //FindIntersection(A, B);   
  20.     int  i = 0, j = 0;  
  21.     int  cnt = 0;  
  22.     int  result[M > N ? M : N]; //保存集合的结果   
  23.     //设置i、j索引，分别指向数组A和B，相等则同时移动，不相等则移动较小值的索引   
  24.     while (i < M && j < N)  
  25.     {  
  26.         if (A[i] == B[j])  
  27.         {  
  28.             result[cnt] = A[i];  
  29.             i++;  
  30.             j++;  
  31.             cnt++;  
  32.         }  
  33.         else   if (A[i] < B[j])  
  34.         {  
  35.             i++;  
  36.         }  
  37.         else   
  38.         {  
  39.             j++;  
  40.         }  
  41.     }  
  42.     for (i = 0; i < cnt; i++)  
  43.     {  
  44.         printf("%4d" , result[i]);  
  45.     }  
  46.     return  0;  
  47. }  
发表于 2014-12-25 11:13:37 回复(0)
提交观点

问题信息

数组 腾讯
来自：腾讯2014校招研发工...
难度：
24条回答 17374浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号