1

如何删除列表的重复项？（运行时间为 O(n log n) ）例如：'(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)))))

这是正确的吗？

4

2 回答 2

2

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

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

(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) reverse它按预期工作，以额外操作为代价保留列表中的原始顺序（这是此问题的一个约束，如评论中所述） ：

(re-dup '(4 6 1 1 2 3 3 5 6))
=> '(4 6 1 2 3 5)
于 2013-07-02T19:07:32.200 回答
0

您可以通过O(n log n)以下方式获得行为：

  1. 合并排序（即O(n log n)）
  2. 遍历并丢弃重复项（即O(n)

因而整体O(n log n)。

(define (re-dup lst)
  (if (null? lst)
      lst
      (let ((lst (list-sort < lst)))
        (let thinning ((skip (car lst)) (rest (cdr lst)))
          (cond ((null? rest) (list skip))
                ((equal? skip (car rest)) (thinning skip (cdr rest)))
                (else (cons skip (thinning (car rest) (cdr rest)))))))))
于 2013-07-02T19:15:14.727 回答