删除 O(nlogn) 中列表的重复项 [英] remove duplicate of a list in O(nlogn)

问题描述

如何删除重复的列表?(运行时间为 O(n log n) )例如:'(4 6 1 1 2 3 3 5 6) => '(4 6 1 2 3 5)

How to remove duplicate of a list? (running time is O(n log n) ) ex: '(4 6 1 1 2 3 3 5 6) => '(4 6 1 2 3 5)

 (define (re-dup lst)
   (cond
      ((empty? lst) empty)
      (else
      (define el (first lst))
      (define el-free-lst (filter (lambda (x) (not (= el x))) (rest lst)))
      (cons el (re-dup el-free-lst)))))

这样对吗?

推荐答案

您当前的解决方案是 O(n^2)，因为 filter 遍历列表一次 对于原始列表中的每个元素.可以使用具有恒定时间插入和成员资格操作的辅助数据结构编写 O(n) 解决方案，以跟踪已经找到的元素.

Your current solution is O(n^2), because filter traverses the list once for each of the elements in the original list. It's possible to write an O(n) solution using a helper data structure with constant time insertion and membership operations to keep track of the elements that have been found already.

在 Racket 中，我们有一个开箱即用的 set 数据结构，对于 恒定时间操作，实际上需要 O(log N) 时间一组大小为 N"(参见 文档)，因此 set-member? 和 set-add 过程将是 O(log n).所以这个使用 Racket 的 set 的实现不是最优的，但我们实现了 O(n log n) 目标:

In Racket, we have an out-of-the-box set data structure which, for constant time operations, "actually requires O(log N) time for a set of size N" (see the documentation), therefore the set-member? and set-add procedures will be O(log n). So this implementation using Racket's set is not optimal, but we achieve the O(n log n) target:

(define (re-dup lst)
  (let loop ((seen (set))
             (lst lst)
             (acc '()))
    (cond ((null? lst)
           (reverse acc))
          ((set-member? seen (car lst))
           (loop seen (cdr lst) acc))
          (else
           (loop (set-add seen (car lst))
                 (cdr lst)
                 (cons (car lst) acc))))))

它按预期工作，以额外的 O(n) 为代价，保留列表中的原始顺序(这是此问题的约束，如注释中所述)反向操作:

It works as expected, preserving the original order in the list (which is a constraint for this problem, as stated in the comments) at the cost of one additional O(n) reverse operation:

(re-dup '(4 6 1 1 2 3 3 5 6))
=> '(4 6 1 2 3 5)

这篇关于删除 O(nlogn) 中列表的重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！