O(n)量級(jí)實(shí)現(xiàn)刪除兩個(gè)數(shù)組中的共同元素
一問(wèn)題描述：
int a1[] , int a2[]都是升序數(shù)組。 a1中可能含有a2[]中的數(shù)。
求：刪除a1中和a2數(shù)組中值相同的數(shù)，并返回a1后數(shù)組有效值個(gè)數(shù)。
要注意的特殊部分：
(1) a1,a2 中的元素都需要進(jìn)行刪除重復(fù)的。
(2)數(shù)組中可能不會(huì)是嚴(yán)格的單調(diào)遞增，會(huì)有相等的數(shù)字。
二 問(wèn)題分析：
/**//*
int a1[] int a2[]都是升序數(shù)組。
a1中可能含有a2[]中的數(shù)。
求：刪除a1中和a2數(shù)組中值相同的數(shù)，并返回a1后數(shù)組有效值個(gè)數(shù)
*/
#include <iostream>
using namespace std ;
const int N = 10 ;
int a[N] = 
{1 , 3 , 7, 7, 8 , 9 , 14 , 15 , 20 , 22}; //此種方法不應(yīng)含有相同的數(shù)字
int b[N] = {2 , 3 , 3, 7 ,15 , 15 ,17 ,19 , 20 , 20};
int lenb ;
int subtract()
{
int i = 0 ; //i表示數(shù)組a中的當(dāng)前下標(biāo)
int j = 0 ; //j表示數(shù)組b中的當(dāng)期下標(biāo)
int lena = N ; //lena表示數(shù)組a中的元素個(gè)數(shù)
lenb = N ; //lenb表示數(shù)組b中的元素個(gè)數(shù)
//建立兩個(gè)變量 分別為samea sameb
//因?yàn)閮蓚€(gè)隊(duì)列中可能會(huì)有相同的數(shù)字
int samea = 0 ;
int sameb = 0 ;
while(i < N && j < N)
{
if(a[i] == b[j])
{
lena-- ;
lenb-- ;
i++ ;
j++ ;
samea++ ;
sameb++ ;
while(i < N) //判斷數(shù)組a中是否有連續(xù)幾個(gè)相等的元素
{
if(a[i-1] == a[i])
{
i++ ;
lena-- ;
samea++ ;
}
else
break ;
}
while(j< N)//判斷數(shù)組b中是否有幾個(gè)連續(xù)相等的元素
{
if(b[j-1] == b[j])
{
j++ ;
lenb-- ;
sameb++ ;
}
else
break ;
}
continue ;
}else
{
a[i - samea] = a[i] ; //不相等的話，則進(jìn)行移除操作
b[j - sameb] = b[j] ; //以后進(jìn)行數(shù)組中，刪除特定的數(shù)字，均可以按照此方法進(jìn)行。
}
if(i < N && a[i] < b[j]) {i++ ; continue ;} //注意此處需要用if，而不需要用while
if(j < N && a[i] > b[j]) j++ ;
}
while(i < N) //循環(huán)完畢之后，將之后的元素，移到前面
a[i - samea] = a[i++] ;
while(j < N)
b[j - sameb] = b[j++] ;
return lena ;
}
int main()
{
int lena = subtract() ;
for(int i = 0 ; i < lena ; i++)
cout<<a[i]<<" " ;
cout<<endl ;
for(int i = 0 ; i < lenb ; i++)
cout<<b[i]<<" " ;
system("pause") ;
return 0 ;
}