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 ;
}