在clojure [script]中，如何在2个排序的向量之间返回最近的元素 [英] In clojure[script], how to return nearest elements between 2 sorted vectors

问题描述

在 clojure [script] ，如何编写一个函数 nearest / strong> a ， b c> b 最近的元素

In clojure[script], how to write a function nearest that receives two sorted vectors a, b and returns for each element of a the nearest element of b?

例如，

(nearest [1 2 3 101 102 103] [0 100 1000]); [0 0 0 100 100 100]

我希望这个解决方案既是惯用的， ： O（n ^ 2）不可接受！

推荐答案

二进制搜索或排序集引起时间复杂度O（n * log m），其中n是（计数a）和m ）。

Using a binary search or a sorted-set incurs a O(n*log m) time complexity where n is (count a) and m (count b).

然而，利用a和b被排序的事实，时间复杂度可以是O（max（n，m））。 / p>

However leveraging the fact that a and b are sorted the time complexity can be O(max(n, m)).

(defn nearest [a b]
  (if-let [more-b (next b)]
    (let [[x y] b
          m (/ (+ x y) 2)
          [<=m >m] (split-with #(<= % m) a)]
      (lazy-cat (repeat (count <=m) x)
        (nearest >m more-b)))
    (repeat (count a) (first b))))


=> (nearest [1 2 3 101 102 103 501 601] [0 100 1000])
(0 0 0 100 100 100 100 1000)

这篇关于在clojure [script]中，如何在2个排序的向量之间返回最近的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！