"黑白逆"数组元素删除法
2005-10-28 yang_wm 点击: 137
最近在写程序的时候用到了删除数组元素的算法.
由于数组很大,用以前的算法,效率很低,
因此不得不想一个更好方法来解决数组元素删除算法.
我先举一个以前的数组元素删除算法的例子:
比如一个数组:int array[100] , i ;
for(i=0;i<100;i++)
array[i];
现在要删除array数组的元素, 那么最坏的情况下的时间复杂度为O(n^2);
比如要删除全部元素,时间复杂度就为O(n ^2);
最好的情况时间复杂度为:O(n );
删除一个元素的的时间复杂度为O(n );
我改进的算法思想:
顺序查找不要删除的元素,然后依次把他们放回数组中
比如数组a[10]={1,2,3......10};
我现在想删除 a[1]==2,和a[5]==6两个元素.
那就把a[0]=a[0];
a[1]=a[2];
a[2]=a[3];
a[3]=a[4];
a[4]=a[6];
a[5]=a[7];
a[6]=a[8];
a[7]=a[9];
看上面的左右数组元素, 左边是连续的,(a[0]......a[7]),而右边是除去a[1],a[5]的元素.
那么给两个指针p1,p2。P2负责查找不要删除的元素，p1负责记录当前元素移动所到的位置,
如果p2找到了不是删除的元素,那么就把p2所指的元素付给p1所指的位置上.
p1 p2
| |
V V
a[0]->a[1]->a[2]->a[3]->a[4]->a[5]->a[6]->a[7]->a[8]->a[9]
不管要删除的元素有多少个,最坏的情况下,时间复杂度都是O(n).
“黑白逆”是指要删除的元素是黑, 不删除的元素是白, 删除原本是对”黑”进行操作,而这种算法则是对不要删除的元素”白”进行操作,所以叫”黑白逆”数组元素删除算法.
杨威
|
