Lisp/列表的交集

Question

你好，我正在尝试在 common-lisp 中创建一个函数，它接受两个列表，并输出它们的交集，假设每个列表中没有重复而不使用交集函数。似乎不起作用。有人可以帮忙吗？

(defun isect (lst_1 lst_2)
    (setq newlist nil)
    (dolist (x lst_1 newlist)
        (dolist (y lst_2) 
            (if (equal x y) (setf newlist (append newlist x)))
        )
    )
)

Answer 1

我假设两个参数均为同一列表的 isect 应该返回一个相等的列表，而不是一个被展平的列表。在这种情况下，(append newlist x) 不会将元素添加到列表末尾。这是我的建议:

(defun intersect (lst-a lst-b &aux result)
  (dolist (a lst-a (nreverse result))
    (dolist (b lst-b)
      (when (equal a b)
        (push a result)))))

这是 O(n^2)，而您可以使用哈希表在 O(n) 内完成。