C++-求N个有序数组的公共元素

Question

具体可以以N个增序的int类型vector为例，求N个vector的公共元素，没有的话输出无。要求时间复杂度尽量低

Answer 1

这是一个NP问题，给出一个解法

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int arr[12]={1,2,3,4,4,5,6,7,3,4,5,6};
vector<int> v1(arr,arr+4),v2(arr+4,arr+8),v3(arr+8,arr+12);
vector<vector<int>*> vs;
vs.push_back(&v2);
vs.push_back(&v3);
vector<int> vshare(v1.begin(),v1.end());
for(int i=0;i<(int)vs.size()&&!vshare.empty();++i)
{
vector<int> *v=vs[i];
/*int a=vshare.front();
int b=v->back();
int c=vshare.back();
int d=v->front();*/
if(vshare.front()>v->back()||vshare.back()<v->front())
{
vshare.clear();
continue;
}
vector<int>::iterator it1=vshare.begin();
vector<int>::iterator it2=v->begin();
while(it1!=vshare.end()&&it2!=v->end())
{
if(*it1<*it2)
it1=vshare.erase(it1);
else if(*it1>*it2)
++it2;
else
{
++it1;
++it2;
}
}
}
if(vshare.empty())
cout<<"没有共同元素"<<endl;
else
{ cout<<"共同元素为 ";
for(int i=0;i<vshare.size();++i)
cout<<vshare[i]<<" ";
cout<<endl;
}
system("pause");
return 0;
}

算法复杂度为O(NM),N为vector数目，M为vector平均长度。