顺序表删除重复值的高效算法。

需求:编写算法,实现删除当前顺序表中所有值为X的元素,并使此操作的时间复杂度为O(n),其中n为线性表的长度。

分析: 1,从顺序表的表头依次扫描,遇到值为X的数据元素就将其删掉,直到扫描最后一个元素。

       顺序表删除一个元素时间复杂度为O(n),要对n个元素处理,所以时间复杂度为O(n^2),不符合题意。

          2,先设计一个计数变量k,用来记录不等于X的值得个数,初始值为0,一边扫描的时候一边统计,当统计到K个不

          等于X的值的数时,将其放到第K个存放位置,最后修改长度为K。

 1 //删除顺序表重复元素
 2     public void del_x(Object x) {
 3         int k=0;
 4         for(int i=0;i<curLen;i++){
 5             if(!listElem[i].equals(x)){
 6                 listElem[k++]=listElem[i];
 7             }
 8         }
 9         curLen=k;
10     }
原文地址:https://www.cnblogs.com/xurui1995/p/5173620.html