除去一个数组中的重复的数据有什么好算法

Question

如题所述

Answer 1

这个问题的意思是，如果假设一个数组中存在重复的数据项，那么就中保留重复数据项中的一个。也就是说最终输出的结果数组中不容许存在重复数据项，所以因为这里涉及到重复数据项的问题，所以立马想到了集合(Set)这个数据结构，因为它是不容序存在重复数据项的数据结构，
思路1.也就是将数组中的所有元素插入到一个Set中，利用Set的自动剔除重复数据项的功能，将导致所有重复数据项没有办法插入成功，也就是add方法
返回false,然后调用toArray方法，返回这个集合所对应的数组。那么这个数组就是一个没有重复数据项的数组，利用这个方法，通过比较结果数组和
源数组之间的大小，查看源数组中到底是否存在重复数据项。
思路2.除了利用Set这个数据结构不容序存在重复数据项的功能之外，还有一种很容易想到的方法，也就是对整个数组进行排序，然后遍历排序之后的数组，将重复数据项，清除掉。
思路1的实现：
public static int[] noDup(int[] array) {

Set<Integer> set = new
HashSet<Integer>();

for (int i :
array)

set.add(i);

Integer[]
integers = (Integer[]) set.toArray();

int[] result
= new int[integers.length];

for (int i =
0; i < integers.length; i++)

result[i] =
integers[i];

return
result;
}

思路2的实现:
使用快速排序等算法对数组进行排序，这个排序过程不在介绍。假设下面这个算法的输入是一个几经排好序的数组。
for (int i = 0; i < array.length - 1; i++) {

if (array[i]
== array[i + 1]) {

array[i] =
-1;

}

}
通过上面这段代码就能够实现把数组中所有的重复数据项只保留一个，其它的置为-1或者根据实际情况置成其它值。然后遍历数据，删除所有位-1的数据项，并且将数组中包含的记录个数不断减少即可。