Question

Java数组去重复问题

输入：一个字符串数组(元素个数可能>100000)，数组内元素有重复（重复程度未知），但有序
输出：一个新字符串数组，无重复元素

效率优先的情况下应该用什么方式处理？（空间占用最好别太大）
考虑过ArrayList，但是在元素个数过大的时候，其新建数组再复制的做法似乎会影响效率和空间？
目前在想的几个方法：
1、遍历一遍数组，确定不重复元素个数，依此新建数组，再遍历一次，边遍历边写入
2、在原字符串基础上遍历，将后面的不重复元素向前覆盖，将覆盖的数组复制出来
3、建立一个递归遍历，递归返回不重复元素的值（同时计算不重复元素个数），在递归到数组尾的时候建立新数组，通过回溯逆向赋值

或者你们有什么更好的方法吗？
谢谢~

例：对于数组
AA，AA，AB，BB，CC，CC，CD，DD，DD，EE，HH，NN，NN，XX
| | | | | | | | |

返回数组：
AA，AB，BB，CC，CD，DD，EE，HH，NN，XX

Answer 1

最简单的方式，我觉得效率也比较高的！ 你建一个set。TreeSet吧，把组数组里面的数据取出来一个一个放入set。最后set里面的数据就是没有重复的了！把set再放回ArrayList就OK。好处是，不管List有多大，放入的时候都是一个一个放的。我尝试过给6万条数据去重复，效率还是可以的

追问

没说要放回ArrayList。。。我只是字符串数组去重而已
假设最糟糕情况下（嗯，比如100000个不重复）的比较次数似乎不少？

追答

不需要比较，放进去，set里面的数据就是你要的值。就放进去，就完了。

Answer 2

代码如下：
public static void main(String[] args) {
int[] Nums = { 100, 2, 2, 3, 4, 5, 5, 5, 7, 7, 8, 9, 9, 23, 45, 75, 75,
78, 80, 99, 99, 199 };
Integer [] aa = getDistinct(Nums);

for(int i : aa){
System.out.println(i);
}
}

static Integer[] getDistinct(int num[]) {
List<Integer> list = new java.util.ArrayList<Integer>();
for (int i = 0; i < num.length; i++) {
if (!list.contains(num[i])) {//如果list数组不包括num[i]中的值的话，就返回true。
list.add(num[i]); //在list数组中加入num[i]的值。已经过滤过。
}
}

return list.toArray(new Integer[0]);
//toArray（数组）方法返回数组。并要指定Integer类型。new
integer[o]的空间大小不用考虑。因为如果list中的长度大于0（你integer的长度），toArray方法会分配一个具有指定数组的运行
时类型和此列表大小的新数组。
}

Answer 3

如果是数组的话，这个空间上是可以重复利用的（从C的角度考虑）。但是如果一定要用ArrayList，那么我想就只能重新开一个ArrayList了，保证扫一遍就去重完成。

追问

没说一定要用ArrayList，只是用ArrayList在元数据量大且重复率低的时候，在此过程中会多次申请空间（每次为上次空间的1.5倍），然后从旧数组拷贝到新数组的过程中，时间消耗会比较大。

无用空间是会抛弃，且可以被重用，但是数组拷贝的时间消耗似乎不小？

追答

如果是C语言的话是不需要要拷贝的，设计可以这样
假设原始数据存在数组int[] a, 长度为n
int l = 1;
for (int i = 1; i < n; i++) {
if (a[i] != a[i - 1])
a[l++] = a[i];
}
这样就可以了，但是java的话，Arraylist写起来就比较蛋疼
int l = 1;
n = a.size();
for (int i = 1; i < n; i++) {
if (!a.get(i).equals(a.get(i - 1))

a.set(l++, a.get(i));

}
return a.subList(0, l);

追问

我一开始就是按你C语言那个想法弄的，后来发现不行。。。
元数据是字符串数组，不是ArrayList。
后面这方法和我的方法2差不多，我再考虑一下

追答

为什么不行，这个和是int类型还是字符串数组有什么关系，不就是判断相等的方式变了而言。

追问

Java里普通数组（不用ArrayList的情况下）一旦设置数组长度就不能改变啊，所以上面那个a[l++] = a[i];的动态增长就没法在Java用了。
之前在Java这么试过，不能用，所以才会纠结。

Answer 4

public class Array{

	public static void main(String[] args) {
		String[] arr = {"AA","AA","AB","BB","CC","CC","CD","DD","DD","EE","HH","NN","NN","XX"};
		java.util.Set<String> set = new java.util.HashSet<String>();
		for(int i = 0; i < arr.length; i++){
			set.add(arr[i]);
		}
		String[] strarr = new String[set.size()];
		int i = -1;
		for(String str : set){
			strarr[++i] = str;
		}
		java.util.Arrays.sort(strarr); //set集合是无序的，用冒泡排序
		System.out.println(java.util.Arrays.toString(strarr)); //输出字符串格式数组的值
	}
}

追问

一定要破坏原本的有序性吗？
把有序性破坏掉重排一次效率损失还是不小的...
（另外String数组使用Arrays.sort应该是堆排序吧？）

追答

Set是无须的，如果不破坏顺序，可以使用ArrayList。

Answer 5

用HashSet 把数组无脑全往里存就行了 他会自动去重 如果要对对象去重
重写equals和hashcode方法 给定equals比较规则

追问

只是字符串去重
放到HashSet之后用toArray写入新数组，但是原本的有序性保留吗?

追答

想要不破坏顺序就用LinkedHashSet 放假了 懒得开电脑才看见 回答晚了 希望能帮你解决