删除重复元素-算法

问题: 删除一个数组里面所有重复的元素？

当然，有很多种解决方法:

1.循环删除:

for(int i = 0; i< 数组.length();i++){
	for(int j = 0 ; j<数组.length(); j++){
		if(j == i){
			删除操作;
		}
	}
}

  这个方法无疑是可以的，但是如果数组长度是100W个元素的话，而这个算法的时间复杂度为:
   t(n^2) 其中n为数组长度，运行时间太长了！！！

下面介绍一种空间换时间的方法(只适合于数值差异范围较小):
2.位对比:

	假设插入的100W个元素均匀分布在0 - 10000 之中，那么可以用1667个long 类型变量来进行位比较: 

	  public static Integer[] deleteRepeat(Integer[] elements){
        long[] a = new long[1667];  #创建1667个64位的long 类型变量
        int index;	# 元素在数组中的索引
        for(int i = 0; i<elements.length;i++){
            index = elements[i] / 64;   # 处于64得到下标索引
            boolean flag = getBit(elements[i], a[index]);  #判断位上是否有元素
            if(!flag){	 #如果没有元素即赋值为1
                a[index] = a[index] | (1 << elements[i] );
            }else{
                elements[i] = null;   #存在即删除元素,这里重点讲算法，所以直接null代替删除操作。
            }
        }
        return elements;   #返回删除元素后的数组
    }

	 public static boolean getBit(int element,long a){
        return ((a >> element) & 1)  ==  1 ;   #判断位上是否存在元素
    }

	算法其实很简单，就是利用位运算，第一个long变量的64个bit 代表 0 - 63，
第二个long变量的64个bit代表64-127......依次类推，假如要寻找数字15是否有重复元素，直接拿出第一个Long变量，对比第十六位上的Bit是否为1,如果是1的话，就证明之前的元素存在15，直接把该元素删除，否则就赋值为1。

	不难看出，上面算法的时间复杂度为: T(数组.长度),而空间复杂度为: T(数组.长度/64),所以该算法只适合与数值差异在没有那么大的范围集合。

如果有讲解错误，请留言联系作者及时删除，避免引导错误。

本文地址：https://blog.csdn.net/weixin_43946878/article/details/109954121