首页 > 代码库 > 有序数组去重的几种算法

有序数组去重的几种算法


最差的算法:

最差的算法:
去重,与数组是否有序无关
public void noDups(){
    //从0开始遍历
    for(int i=0; i<nElems-1; i++){
        //与后面每一个比较
        for(j=i+1; j<nElems; j++){
            //如果相等,后面的所有的项向前移动,总数-1
            if(a[i]==a[j]){
                for(k=j+1; k<nElems; k++){
                    a[j] = a[j+1];
                    nElems--;
                }
            } 
        }
    }
}

把后面不同的往前
public void noDups(){
    //数组从小到大排列
    this.insertionSort();
    int i=0;    //第一个指针
    int j=0;    //第二个指针
    for(j=1; j<nElems;j++){
        //遇到相同的跳过,不同的则加到前面
        if(a[j]!=a[i]){
            a[++i]=a[j]
        }
    }
    nElems = i+1;
}

把重复的标记为-1,假设没有负数
public void noDups(){
    //数组从大到小排列
    this.insertionSort();
    final int FLAG = -1;    //重复数字标记
    int holdNumber; //被标记的数字个数
    //寻找重复项并标记
    for(int i=0; i<nElems; i++){
        for(int j=i+1; j<nElems; j++){
            if(a[i]==a[j]){
                a[j] = FLAG;
                holdNumber++;
            }
        }       
    }

    //处理被标记的数字
    //思路和第一个一样
    int i=0; //索引位
    for(int j=1; j<nElems; j++){    //第一个不可能是重复数
        //找到第一个标记位
        if(a[j]==FLAG && i==0){
            i = j;
        }else if(a[j]!=FLAG && i!=0){   //逻辑同第二个算法
            a[i] = a[j];
            i++;
        }
    }
    nElems -= holdNumber;

}