2

假设我们有一个整数列表：1, 2, 5, 13, 6, 5, 7我想找到第一个重复的数字并返回两个索引的向量。在我的示例中，它是 5 at [2, 5]。到目前为止我所做的是loop，但我可以做得更优雅，更短吗？

(defn get-cycle
  [xs]
  (loop [[x & xs_rest] xs, indices {}, i 0]
    (if (nil? x)
      [0 i]  ; Sequence is over before we found a duplicate.
      (if-let [x_index (indices x)]
        [x_index i]
        (recur xs_rest (assoc indices x i) (inc i))))))

无需返回数字本身，因为我可以通过索引获取它，其次，它可能并不总是存在。

4

5 回答 5

6

使用列表处理的选项，但不是更简洁：

(defn get-cycle [xs]
  (first (filter #(number? (first %))
    (reductions
      (fn [[m i] x] (if-let [xat (m x)] [xat i] [(assoc m x i) (inc i)]))
      [(hash-map) 0] xs))))
于 2013-11-10T22:12:17.647 回答
4

这是一个使用reduce来在找到第一个重复项时停止使用序列的版本：

(defn first-duplicate [coll]
  (reduce (fn [acc [idx x]]
            (if-let [v (get acc x)]
              (reduced (conj v idx))
              (assoc acc x [idx])))
          {} (map-indexed #(vector % %2) coll)))
于 2013-11-10T23:21:53.787 回答
1

我知道你只要求第一个。这是一个完全惰性的实现，每步分配开销很小

(defn dups
[coll]
(letfn [(loop-fn [idx [elem & rest] cached]
      (if elem
          (if-let [last-idx (cached elem)]
        (cons [last-idx idx]
              (lazy-seq (loop-fn (inc idx) rest (dissoc cached elem))))
        (lazy-seq (loop-fn (inc idx) rest (assoc cached elem idx))))))]
  (loop-fn 0 coll {})))

(first (dups v))
=> [2 5]

编辑：以下是一些标准基准：

被接受的答案：7.819269 µs

这个答案(first (dups [12 5 13 6 5 7]))：6.176290 µs

贝沙斯特尼：5.841101 µs

第一次复制：5.025445 µs

于 2013-11-11T03:33:05.240 回答
0

您的代码的意图似乎与您在评论中的描述不同，所以我并不完全相信我理解。也就是说，loop/recur绝对是解决问题的有效方法。

这是我想出的：

(defn get-cycle [xs]
  (loop [xs xs index 0]
    (when-let [[x & more] (seq xs)]
      (when-let [[y] (seq more)]
        (if (= x y)
          {x [index (inc index)]}
          (recur more (inc index)))))))

这会将重复项目的映射返回到该项目所在的两个索引的向量。

(get-cycle [1 1 2 1 2 4 2 1 4 5 6 7])
;=> {1 [0 1]}

(get-cycle [1 2 1 2 4 2 1 4 5 6 7 7])
;=> {7 [10 11]}

(get-cycle [1 2 1 2 4 2 1 4 5 6 7 8])
;=> nil

这是使用序列函数的替代解决方案。我更喜欢这种方式，但它是否更短或更优雅可能是主观的。

(defn pairwise [coll]
  (map vector coll (rest coll)))

(defn find-first [pred xs]
  (first (filter pred xs)))

(defn get-cycle [xs]
  (find-first #(apply = (val (first %)))
              (map-indexed hash-map (pairwise xs))))

根据@demi 的说明进行编辑

啊，明白了。这是你的想法吗？

(defn get-cycle [xs]
  (loop [xs (map-indexed vector xs)]
    (when-let [[[i n] & more] (seq xs)]
      (if-let [[j _] (find-first #(= n (second %)) more)]
        {n [i j]}
        (recur more)))))

我重用find-first了我之前基于序列的解决方案。

于 2013-11-10T21:41:26.090 回答
0

实际上，loop除非您想查找所有重复项，否则这是一个不错的选择。reduce即使在没有必要的情况下，诸如此类的事情也会导致对输入序列的全面扫描。

这是我的版本get-cycle：

(defn get-cycle [coll]
  (loop [i 0 seen {} coll coll]
    (when-let [[x & xs] (seq coll)]
      (if-let [j (seen x)]
        [j i]
        (recur (inc i) (assoc seen x i) xs)))))

与您的唯一区别get-cycle是我的版本nil在没有重复时返回。

于 2013-11-10T22:23:32.917 回答