[关闭]
@zero1036 2017-03-31T18:36:17.000000Z 字数 984 阅读 3484

最优去重算法探索

数据结构与算法 Java-Base


去重需求

  1. 去重
  2. 要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10

算法设计

双层遍历实现

实现逻辑:遍历源数组,依次比较当前元素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:

  1. private static void removeDuplicateByList(int[] arr) {
  2. List<Integer> target = new ArrayList<Integer>(); //处理结果数组
  3. startWatch();
  4. for (int i = 0; i < arr.length; i++) {
  5. if (arr[i] == -1) continue;
  6. for (int j = i + 1; j < arr.length; j++) {
  7. if (arr[i] == arr[j]) { //记录重复元素下标
  8. arr[j] = -1;
  9. }
  10. }
  11. target.add(arr[i]);
  12. }
  13. stopWatch();
  14. }

Hash实现

实现逻辑:Set是一个不包含重复元素的collection,其本质是Map,通过元素的hashCode确定在Map数组的位置下标,相同位置下标且值不等,且入链表;相同位置下标且值相等则排除;理论上,最优情况是样本数组全部数据hash下标不相同,无需进行equal()比较,时间复杂度为O(1)

时间复杂度:最优情况

最坏情况

样本数据:正整数数组,只有一项为重复项,99%不重复

执行结果耗时:

样本数 耗时
10w 0.016s
20w 0.023s
30w 0.025s
100w 0.198s

Code:

  1. private static void removeDuplicateBySet(int[] arr) {
  2. Set<Integer> target = new LinkedHashSet<Integer>();
  3. startWatch();
  4. for (int i = 0; i < arr.length; i++) {
  5. target.add(arr[i]);
  6. }
  7. stopWatch();
  8. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注