问题描述:

Example:

`1 1 1 3 3 4 4 5 5 6 L1`

1 3 3 4 5 L2

1 1 4 5 6 Res

Constraints:

- The diff/subtract is defined as the "set" of elements from L1 minus (∖) L2
- L2 is always a subset (⊆) of L1
- The elements in L1 and L2 can have duplicates
- The elements are primitives (int, string) and all of the same type

`(clojure.set/difference)`

doesn't help here because of (3).

```
(defn diff [s1 s2]
(mapcat
(fn [[x n]] (repeat n x))
(apply merge-with - (map frequencies [s1 s2]))))
```

For example, given

```
(def L1 [1 1 1 3 3 4 4 5 5 6])
(def L2 [1 3 3 4 5 ])
```

then

```
(diff L1 L2)
;(1 1 4 5 6)
```

Here is one way to do it. Steps:

```
1.Find the frequencies for each list
2.Diff the frequencies
3.Repeat each element for the remaining value of frequency.
(defn myminus [s1 s2]
(let [g1 (frequencies s1)
g2 (frequencies s2)
m (merge-with - g1 g2)
r (mapcat #(repeat (second %) (first %)) m)]
r))
```

If inputs are in order, as they appear to be, then you can do this lazily

```
(defn sdiff
[[x & rx :as xs] [y & ry :as ys]]
(lazy-seq
(cond
(empty? xs) nil
(empty? ys) xs
:else (case (compare x y)
-1 (cons x (sdiff rx ys))
0 (sdiff rx ry)
+1 (sdiff xs ry)))))
```

Given example:

```
(def L1 [1 1 1 3 3 4 4 5 5 6])
(def L2 [1 3 3 4 5])
(sdiff L1 L2) ;=> (1 1 4 5 6)
```

Lazy-sequence of numbers that are not Fibonacci numbers. (Notice we don't require constraint #2 -- the repeated 1's in the Fibonacci numbers do not cause a problem.)

```
(defn fibs [] (map first (iterate (fn [[c n]] [n (+ c n)]) [0 1])))
(take 20 (sdiff (range) (fibs)))
;=> (4 6 7 9 10 11 12 14 15 16 17 18 19 20 22 23 24 25 26 27)
```

Since `L2`

is always a subset of `L1`

you can `group-by`

on both lists and just emit the key as many times as the difference is between the counts of each grouping.

```
(def L1 (list 1 1 1 3 3 4 4 5 5 6))
(def L2 (list 1 3 3 4 5 ))
(defn diff [l1 l2]
(let [a (group-by identity l1)
b (group-by identity l2)]
(mapcat #(repeat
(-
(count (second %))
(count (get b (key %))))
(key %)) a)))
(diff L1 L2)
;;(1 1 4 5 6)
```

```
(defn diff-subtract
"The diff-subtract is defined as the sum of elements from L1 minus L2"
[list1 list2]
(let [l1 (into {} (map #(vector (first %) %) (partition-by identity (sort list1))))
l2 (into {} (map #(vector (first %) %) (partition-by identity (sort list2))))]
(-> (map
#(repeat (- (count (l1 %)) (count (l2 %))) %)
(range 1 (inc (apply max (map first l1)))))
flatten)))
(diff-subtract [1 1 1 3 3 4 4 5 5 6] [1 3 3 4 5]) => (1 1 4 5 6)
```