代码之家 › 专栏 › 技术社区 › R u c k s a c k

如何在Clojure中实现整数计数排序?

counting-sort clojure sorting

R u c k s a c k · 技术社区 · 7 年前

假设我有一个整数数组 xs 从中获取值 0 到 max ,我需要在O(n)时间内排序,所以我不能 (sort xs) .

有没有办法用 frequencies 作用

用另一种语言,我会 for 迭代整数的步骤 0 到 最大值 ,对于每个值 x 在该范围内,查找 (frequencies x) 然后做 repeat (frequencies x) x 或者别的什么。

至关重要的是,我需要按照从最小到最高的顺序来做这件事,这就是整个事情的排序。所以我不想 map 中的每个数字 xs型 .

有没有关于clojure式惯用解决方案的想法?

谢谢

2 回复 | 直到 7 年前

Lee 7 年前

更新向量并不完全是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)))))

cfrick 7 年前

你可以照你对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))))

推荐文章

Freid001 · 具有最小和最大限制的架构?

7 年前

R u c k s a c k · 如何创建一个集合列表,其中没有两首连续的歌曲在同一个键中

7 年前

Evgeniy Berezovsky · lein uberjar导致“方法代码太大!”

7 年前

phlie · Hoplon With Castra加载后端时出错

7 年前

David Furnam · Clojure从数组中获取坐标

7 年前

podomunro · 如何在Clojure中按给定日期过滤JSON数据?

7 年前

Jdv · 将贴图M转换为贴图A数组,其中M中的键和值映射到A中元素中的新键

7 年前

Akisame · ClojureScript-外部文件中未定义名称goog

7 年前

Jeroen · 如何将惰性序列转换为映射?

7 年前

bpereira · 使用交换!而不是重置!在atom-clojure中

7 年前