@zero1036
2017-03-31T18:36:17.000000Z
字数 984
阅读 3484
数据结构与算法
Java-Base
实现逻辑:遍历源数组,依次比较当前元素arr[n]
与arr[n + 1]
...arr[last]
,若相等标识重复元素,切记录唯一项到结果target。
时间复杂度:循环了(n+n-1+n-2+...+1)≈(n^2)/2,因为时间复杂度是不考虑系数的,所以是
样本数据:正整数数组,只有一项为重复元素,99%不重复
执行结果耗时:
样本数 | 耗时 |
---|---|
10w | 1.247s |
20w | 4.971s |
30w | 36.773s |
Code:
private static void removeDuplicateByList(int[] arr) {
List<Integer> target = new ArrayList<Integer>(); //处理结果数组
startWatch();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == -1) continue;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) { //记录重复元素下标
arr[j] = -1;
}
}
target.add(arr[i]);
}
stopWatch();
}
实现逻辑:Set
是一个不包含重复元素的collection,其本质是Map
,通过元素的hashCode确定在Map数组的位置下标,相同位置下标且值不等,且入链表;相同位置下标且值相等则排除;理论上,最优情况是样本数组全部数据hash下标不相同,无需进行equal()
比较,时间复杂度为O(1)
时间复杂度:最优情况
样本数据:正整数数组,只有一项为重复项,99%不重复
执行结果耗时:
样本数 | 耗时 |
---|---|
10w | 0.016s |
20w | 0.023s |
30w | 0.025s |
100w | 0.198s |
Code:
private static void removeDuplicateBySet(int[] arr) {
Set<Integer> target = new LinkedHashSet<Integer>();
startWatch();
for (int i = 0; i < arr.length; i++) {
target.add(arr[i]);
}
stopWatch();
}