假设我有一个整数xs
数组从0
到max
的值,我需要在O(n)时间排序,所以我不能只做(sort xs)
。
有没有办法用frequencies
函数做到这一点?
在另一种语言中,我会做一个for
迭代从0
到max
的整数,并且在该范围内的每个值x
,查找(frequencies x)
然后做repeat (frequencies x) x
或其他东西。
至关重要的是,我需要在从最小到最高的顺序中执行此操作,这就是整个事情的一种选择。所以我不想只是map
xs
中的每个数字。
关于clojure-ish惯用解决方案的任何想法?
谢谢。
更新向量不是O(1),但您可以使用它来为每个元素创建计数:
(defn counting-sort [s]
(if (empty? s)
s
(let [counts (reduce (fn [v e]
(update v e inc))
(vec (repeat (inc (apply max s)) 0))
s)]
(apply concat (map-indexed #(repeat %2 %1) counts)))))
那么你可以用clojure做你说的话:
(let [xs [1 2 1 4 1 5 1 8 7 7 7]
fs (frequencies xs)
max 10]
(into []
cat
(for [i (range max) :when (contains? fs i)]
(repeat (get fs i) i))))