list - 如何在列表中找到不常见的项目（互斥）

Question

我的任务是编写一个方案函数，该函数可以生成一个新列表，其中包含仅存在于两个输入列表之一中的元素。我设法创建了一个可行的解决方案：

(define remove
  (lambda (l item)
    (filter (lambda (x) (not (equal? x item))) l)))

(define uncommon_list
  (lambda (list1 list2)
    (cond 
      ((null? list2) list1)
      ((null? list1) list2)
      ((memv (car list1) list2)
       (uncommon_list (cdr list1) (remove list2 (car list1))))
      (else 
       (append (list (car list1)) (uncommon_list (cdr list1) list2))))))       

但是我觉得我把这个复杂化了，而且 O 复杂性不是很好？任何使这一点变得更好的指针都会很棒！谢谢

标签： listfunctional-programmingsetschemeboolean-operations

Answer 1

对于最佳大 O，即 O(n)，您需要创建集合，在 Scheme 中这意味着哈希表。解决方案是更新哈希，以便知道它是否在第一个、第二个或两个列表中找到。然后由不在两者中的元素组成一个列表：

#!r6rs

(import (rnrs base)
        (srfi :69))

(define (uncommon-elements l1 l2)
  (define hash (make-hash-table eqv?))
  (define (update-elements proc default lst)
    (for-each
     (lambda (e)
       (hash-table-update! hash e proc (lambda () default)))
     lst))

  (update-elements values 1 l1)
  (update-elements (lambda (e) (if (= e 2) 2 3)) 2 l2)
  (hash-table-fold hash
                   (lambda (k v acc)
                     (if (= v 3)
                         acc
                         (cons k acc)))
                   '()))

(uncommon-elements '(1 2 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)

(uncommon-elements '(1 1 2 2 3 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)