从序列中取出 n 个最小数字的最有效方法是什么,
[ [1 2 3] [9 2 1] [2 3 4] [5 6 7] ]
我想根据第一项从序列中取最小的 2,
[1 2 3] [2 3 4]
目前我正在对整个列表进行排序,然后取前 n 个项目,但这可能不是最有效的方法,这是一个很大的列表,我需要经常这样做。
最佳答案
Joy of Clojure ,第 6.4 章描述了惰性排序算法。惰性排序的优点在于它只会做必要的工作来找到第一个 x 值。所以如果 x << n 这个算法是 O(n)。这是该算法的修改版本。
(defn sort-parts
[work f]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [psmaller? (partial f pivot)]
(recur (list* (filter psmaller? xs)
pivot
(remove psmaller? xs)
parts)))
(when-let [[x & parts] parts]
(cons x
(sort-parts parts f)))))))
(defn qsort [xs f] (sort-parts (list xs) f))
(defn cmp [[a _ _] [b _ _]] (> a b))
(def a [[1 2 3] [9 2 1] [2 3 4] [5 6 7]])
(take 2 (qsort a cmp))
关于algorithm - 获取序列中 n 个最小的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7624768/