算法5：求兩個(gè)已排序數(shù)組的交集和并集

2019-11-06 06:41:52

字體：大中小

供稿：網(wǎng)友

問題描述

求兩個(gè)已排序數(shù)據(jù)的交集和并集，要求時(shí)間復(fù)雜度為O(m+n).

解題思路

A數(shù)組和B數(shù)組，A數(shù)組大小為m，B數(shù)組大小為n。 1、查找B數(shù)組的每個(gè)成員是否在A數(shù)組中，時(shí)間復(fù)雜度為O(mn) 2、由于A和B數(shù)組都是有序數(shù)組，使用二分法查找B數(shù)組的每個(gè)成員是否在A數(shù)組中，時(shí)間復(fù)雜度為O(n*lgm)。如果n比m大，則查找A數(shù)組的成員是否在B數(shù)組中，時(shí)間復(fù)雜度為O(m*lgn)。 3、使用hash表，將A數(shù)組的值使用hash表保存，B中的值判斷是否存在A中，由于hash表的查找時(shí)間復(fù)雜度為O(1)，所以該算法的時(shí)間復(fù)雜度為O（n）。但是此方法只適合m比較小的情況，如果A數(shù)組比較大，hash表容易產(chǎn)生collision的情況，hash表的查找平均速度將不再是O(1)。 4、使用兩個(gè)指針分別指向數(shù)組A和數(shù)組B，指向數(shù)據(jù)小的指針往前繼續(xù)移動(dòng)，保存兩個(gè)指針指向相同數(shù)據(jù)的值，直到兩個(gè)指針都指向數(shù)組末尾，該算法的時(shí)間復(fù)雜度為O(m+n)。

交集就是保存兩個(gè)指針指向相同的值，并集就是保存兩個(gè)指針指向不同的值，并且保存一份指向相同的值

C++代碼

//獲取兩個(gè)排序數(shù)組的交集void GetIntersectionSet(int ABuffer[],int ALength, int BBuffer[],int BLength,vector<int>& intersectionSet){ int pointerA = 0; int pointerB = 0; while(pointerA < ALength && pointerB < BLength) { if(ABuffer[pointerA] < BBuffer[pointerB]) { pointerA++; } else if(BBuffer[pointerB] < ABuffer[pointerA]) { pointerB++; } else { intersectionSet.push_back(ABuffer[pointerA]); pointerA++; pointerB++; } }}//獲取兩個(gè)排序數(shù)組的并集void GetUnionSet(int ABuffer[],int ALength, int BBuffer[],int BLength,vector<int>& unionSet){ int pointerA = 0; int pointerB = 0; while(pointerA < ALength && pointerB < BLength) { if(ABuffer[pointerA] < BBuffer[pointerB]) { unionSet.push_back(ABuffer[pointerA]); pointerA++; } else if(BBuffer[pointerB] < ABuffer[pointerA]) { unionSet.push_back(BBuffer[pointerB]); pointerB++; } else { unionSet.push_back(ABuffer[pointerA]); pointerA++; pointerB++; } } if(pointerA < ALength) { for(int i = pointerA; i < ALength;i++) { unionSet.push_back(ABuffer[i]); } } if(pointerB < BLength) { for(int i = pointerB; i < BLength;i++) { unionSet.push_back(BBuffer[i]); } }}

測(cè)試代碼

int _tmain(int argc, _TCHAR* argv[]){ //定義排序數(shù)組A和B const int length = 6; int ABuffer[length] = {0}; int BBuffer[length] = {0}; cout<<"please input orderly A Buffer:"<<endl; for(int i = 0; i < length; i++) { cin>>ABuffer[i]; } cout<<"please input orderly B Buffer:"<<endl; for(int i = 0; i < length; i++) { cin>>BBuffer[i]; } //定義交集集合和并集集合 vector<int> intersectionSet; intersectionSet.clear(); vector<int> unionSet; unionSet.clear(); GetIntersectionSet(ABuffer,length,BBuffer,length,intersectionSet); GetUnionSet(ABuffer,length,BBuffer,length,unionSet); //輸出交集和并集 cout<<"the intersection set of orderly A and orderly B as follows:"<<endl; vector<int>::iterator itA; for(itA = intersectionSet.begin(); itA != intersectionSet.end();itA++) { cout<<*itA<<" "; } cout<<endl; cout<<"the union set of orderly A and orderly B as follows:"<<endl; vector<int>::iterator itB; for(itB = unionSet.begin(); itB != unionSet.end();itB++) { cout<<*itB<<" "; } cout<<endl; return 0;}

上一篇：webx3學(xué)習(xí)之旅——webx項(xiàng)目的創(chuàng)建（maven命令創(chuàng)建）

下一篇：初步了解ci