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

推荐

REDStone

如果是有序的用二路归并求交集

如果是无序的可以用map或hash

发表于 2014-11-03 16:54:53 回复(1)

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

直接用并查集就可以求解了呀，效率是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.

参考答案：

如果是有序的用二路归并求交集

如果是无序的可以用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

一个哈希记录小集合,遍历大的集合查找是否存在

发表于 2014-10-25 00:26:03 回复(0)

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

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 <stdio.h> </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<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<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<20; i++) </div> <div> <span> </span>{ </div> <div> <span> </span>if(c[i] >= 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

<?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

如果数据合适可以使用位图或者hash_map，时间复杂度均为 O(n)

发表于 2015-08-04 16:16:25 回复(0)

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

既然是集合，类似于set，就假设集合整数是不重复的。

方法一：

数字不大。hash。或者hash加链式结构

方法二：

A进行排序，归并，堆，快排等都行，B进行二分查找。

发表于 2015-04-08 14:10:17 回复(0)

徐度灿

#include <stdio.h>
#include <stdlib.h>
#define M 8
#define N 5
int cmp( const void *a, const void *b)
{
int *x = ( int *)a;
int *y = ( int *)b;
return (*x) - (*y);
}
int main( void )
{
int A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};
int B[] = {39 ,8 , 10, 6, -1};
//对数组A和数组B进行快排
qsort(A, M, sizeof ( int ), cmp);
qsort(B, N, sizeof ( int ), cmp);
//FindIntersection(A, B);
int i = 0, j = 0;
int cnt = 0;
int result[M > N ? M : N]; //保存集合的结果
//设置i、j索引，分别指向数组A和B，相等则同时移动，不相等则移动较小值的索引
while (i < M && j < N)
{
if (A[i] == B[j])
{
result[cnt] = A[i];
i++;
j++;
cnt++;
}
else if (A[i] < B[j])
{
i++;
}
else
{
j++;
}
}
for (i = 0; i < cnt; i++)
{
printf("%4d" , result[i]);
}
return 0;
}

发表于 2014-12-25 11:13:37 回复(0)

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

问题信息

热门推荐

相关试题