浅议“删除向量（数组）中多余元素”的基本操作及其优化
浅议“删除向量（数组）中多余元素”的基本操作及其优化巧若拙
向量（数组）是一种紧凑的数据结构，向量的各种基本操作代码简单，容易理解，但由于在执行“插入”和“删除”操作时，需要移动大量元素，尤其在删除多个元素时，可能会产生大量重复移动，效率低下。
本文以“删除一个有序向量中多余的值相同的元素”为例，分析“删除向量中多余元素”的基本操作及其优化方法。
一，基本思想：
该算法的基本思想是：由于向量中的元素按元素值非递减有序排列，值相同的元素必为相邻的元素，因此依次比较相邻的两个元素，若值相等，则删除其中一个，否则继续向后查找，最后返回向量的新的长度。代码如下：
int DelSameElem_1(int vec[], int n)
{
int i, j;
i = 0;
while (i < n-1)
{
if (vec[i] != vec[i+1])
{
i++;
}
else //每检测到一个相同元素，即删除多余的一个
{
for (j=i; j<n-1; j++)
{
vec[j] = vec[j+1];
}
n--;
}
}
return n;
}
二，第一步优化
在基础算法中，每检测到一个多余相同元素，即进行删除操作，导致大量重复移动，效率低下。如果能够将多余元素整块删除的话，可以减少重复移动，提高效率。
我们通过一个实例来分析整块删除方法：
初始向量：vec[8] = {1,2,2,2,2,2,3,4}。
向量中值为“2”的元素共有5个，其中有4个是多余的，我们可以将vec[6..7]一次性前移，覆盖掉需要删除的多余元素，并将向量长度减4，即得到新的向量：
vec[4] = {1,2,3,4}。
改进后代码如下：
int DelSameElem_2(int vec[], int n) //改进版1：整块删除多余相同元素
{
int i, j, k;
for (k=0,i=1; i<n; i++)
{
if (vec[i] == vec[i-1])
{
k++; //累计多余的相同元素个数
}
else if (k > 0) //整块删除多余的元素
{
for (j=i; j<n; j++)
{
vec[j-k] = vec[j];
}
i -= k;
n -= k;
k = 0;
}
}
return n - k; //尾部的多余元素直接去掉
}
三，第二步优化
在改进版1中，我们可以一次性删除一整段多余元素，减少了一些重复移动，但是，如果向量中存在多段多余元素时，后面的元素难免被多次重复移动，效率依然不高。
我们通过一个实例来分析：
初始向量：vec[10] = {2,2,2,2,3,3,3,4,4,4}。
第一次删除：将vec[4..9]一次性前移，覆盖掉值为“2”的多余元素，得到新的向量：vec[7] = {2,3,3,3,4,4,4}。
第二次删除：将vec[4..6]一次性前移，覆盖掉值为“3”的多余元素，得到新的向量：vec[5] = {2,3, 4,4,4}。
最后将尾部的多余元素直接去掉，得到新的向量：vec[3] = {2,3, 4}。
我们发现，在上面的实例中，值为“3”的元素移动了一次，值为“4”的元素移动了2次——还是有重复移动。能否让每个元素都只移动一次就实现删除功能呢？
可以。代码如下：
int DelSameElem_3(int vec[], int n) //改进版2：高效覆盖多余相同元素，达到删除目的
{
int i, k;
for (k=0,i=1; i<n; i++)
{
if (vec[i] == vec[i-1])
{
k++;
}
else
{
vec[i-k] = vec[i];
}
}
return n-k;
}
四，更一般化的删除向量元素的方法
前面的例子我们分析了“删除一个有序向量中多余的值相同的元素”，实际需要我们删除满足某种条件的若干元素，我们可以设计一个标记函数，把满足删除条件的元素改为标记值，然后进行高效删除。代码如下：
void Mark(int vec[], int n, int tag)// 满足删除条件的元素改为标记值
{
int i;
for (i=1; i<n; i++)
{
if (vec[i-1] == vec[i])
{
vec[i-1] = tag;
}
}
}
int DelElem(int vec[], int n)
{
int i, k;
int tag = vec[0] - 1; //将需要被删除的元素赋值为tag
Mark(vec, n, tag);
for (k=0,i=0; i<n; i++)
{
if (vec[i] == tag)
{
k++;
}
else
{
vec[i-k] = vec[i];
}
}
return n-k;
}
