两个列表中的公共元素具有重复 [英] Common elements in two lists with duplicates

问题描述

 （列表，向量，序列）中的常用元素。共同元素[1] [1]）; [1] 
（common-elements [1 2] [1 1]）; [1] 
（common-elements [11] [1 1 1]）; [1 1] 
  

这里是我目前有的：

 （defn remove-first [elem coll] 
（lazy-seq 
（when-let [s（seq coll）] 
 （let [f（first s），r（rest s）] 
（if（= elem f）
r 
（cons f（remove-first elem r））））））））） 
 
（defn common-elements [coll1 coll2] 
（lazy-seq 
（when（and（seq coll1）（seq coll2））
（let [f （first coll1）] 
（if（some＃{f} coll2）
（cons f（common-elements（rest coll1）
（remove-first f coll2）））
（common-elements（rest coll1）coll2））））
  

=http://www.4clojure.com/ =nofollowtitle =4clojure> 4clojure 告诉我，我很少写最惯用的或简洁的代码，所以我有兴趣了解是否有更好的方法。

解决方案

这是我的实现。它使用映射和集合来保存中间数据，因此不像你的版本那样懒惰，但我认为它更可读，并且将具有更好的整体性能特性（你的版本有二次时间复杂性来实现公共元素的结果）。

 （require'[clojure.set：as set]）
（defn common-elements [& colls] 
（let [freqs（map frequencies colls）] 
（mapcat（fn [e]（repeat（apply min（map＃（％e）freqs））e））
 / intersection（map（comp set keys）freqs）））））
  

I want to find the common elements in two [lists, vectors, sequences] when there can be duplicates.

(common-elements [1] [1]) ; [1]
(common-elements [1 2] [1 1]) ; [1]
(common-elements [1 1] [1 1 1]) ; [1 1]

Here is what I currently have:

(defn remove-first [elem coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (let [f (first s), r (rest s)]
        (if (= elem f) 
          r 
          (cons f (remove-first elem r)))))))

(defn common-elements [coll1 coll2]
  (lazy-seq
    (when (and (seq coll1) (seq coll2))
      (let [f (first coll1)]
        (if (some #{f} coll2)
          (cons f (common-elements (rest coll1)
                                   (remove-first f coll2)))
          (common-elements (rest coll1) coll2)))))

My experience with 4clojure has shown me that I rarely write the most idiomatic or succinct code so I'm interested in finding out whether there is a better way of doing this.

解决方案

Here's my implementation. It uses maps and sets to hold intermediate data, and thus is not lazy like your version, but I think it is more readable and will have better overall performance characteristics (your version has quadratic time complexity to realize the results from common-elements).

(require '[clojure.set :as set])
(defn common-elements [& colls]
  (let [freqs (map frequencies colls)]
    (mapcat (fn [e] (repeat (apply min (map #(% e) freqs)) e))
            (apply set/intersection (map (comp set keys) freqs)))))

这篇关于两个列表中的公共元素具有重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！