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) 中完成。