O(n)量級實現刪除兩個數組中的共同元素
一問題描述：
int a1[] , int a2[]都是升序數組。 a1中可能含有a2[]中的數。
求：刪除a1中和a2數組中值相同的數，并返回a1后數組有效值個數。
要注意的特殊部分：
(1) a1,a2 中的元素都需要進行刪除重復的。
(2)數組中可能不會是嚴格的單調遞增，會有相等的數字。
二 問題分析：
/**//*
int a1[] int a2[]都是升序數組。
a1中可能含有a2[]中的數。
求：刪除a1中和a2數組中值相同的數，并返回a1后數組有效值個數
*/
#include <iostream>
using namespace std ;
const int N = 10 ;
int a[N] = 
{1 , 3 , 7, 7, 8 , 9 , 14 , 15 , 20 , 22}; //此種方法不應含有相同的數字
int b[N] = {2 , 3 , 3, 7 ,15 , 15 ,17 ,19 , 20 , 20};
int lenb ;
int subtract()
{
int i = 0 ; //i表示數組a中的當前下標
int j = 0 ; //j表示數組b中的當期下標
int lena = N ; //lena表示數組a中的元素個數
lenb = N ; //lenb表示數組b中的元素個數
//建立兩個變量 分別為samea sameb
//因為兩個隊列中可能會有相同的數字
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) //判斷數組a中是否有連續幾個相等的元素
{
if(a[i-1] == a[i])
{
i++ ;
lena-- ;
samea++ ;
}
else
break ;
}
while(j< N)//判斷數組b中是否有幾個連續相等的元素
{
if(b[j-1] == b[j])
{
j++ ;
lenb-- ;
sameb++ ;
}
else
break ;
}
continue ;
}else
{
a[i - samea] = a[i] ; //不相等的話，則進行移除操作
b[j - sameb] = b[j] ; //以后進行數組中，刪除特定的數字，均可以按照此方法進行。
}
if(i < N && a[i] < b[j]) {i++ ; continue ;} //注意此處需要用if，而不需要用while
if(j < N && a[i] > b[j]) j++ ;
}
while(i < 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 ;
}