算法－－"黑白逆"数组元素删除法

"黑白逆"数组元素删除法

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).
“黑白逆”是指要删除的元素是黑, 不删除的元素是白, 删除原本是对”黑”进行操作,而这种算法则是对不要删除的元素”白”进行操作,所以叫”黑白逆”数组元素删除算法.

杨威