使用函数样式合并两个数组

Question

我正在研究如何合并两个排序的数组,并努力使用Java 8流转换解决方案的问题之一.但仍然没有成功.实际上,我没有什么用处可以在这里分享.

必须有一种方法来使用函数式编程中的索引来处理这样的循环.在不改变时间复杂度的情况下,如何在Scala,Clojure等其他语言中完成这项工作？可能那时我可以尝试用Java复制它.

编辑:代码提到问题是最有效的,我不想妥协它.

Answer 1

事实上,到处都有相同的方法:你重复两个集合,将最少的集合头部添加到结果中,然后重复使用其余集合,直到其中一个集合(或两者)为空.在clojure中:

(defn merge-sorted [pred coll1 coll2]
  (loop [coll1 coll1 coll2 coll2 res []]
    (cond (or (empty? coll1) (empty? coll2)) (concat res coll1 coll2)
          (pred (first coll1) (first coll2)) (recur (rest coll1)
                                                    coll2
                                                    (conj res (first coll1)))
          :else (recur coll1 (rest coll2) (conj res (first coll2))))))

user> (merge-sorted < [1 3 5 6 7 8 9 40 50] [1 2 5 10 100])
(1 1 2 3 5 5 6 7 8 9 10 40 50 100)

Answer 2

我认为这很容易用尾递归表达:

def merge(x: List[Int], y: List[Int]): List[Int] = {
  def loop(xss: List[Int], yss: List[Int], acc: List[Int]) = (xss, yss) match {
    case (x :: xs, y :: ys) if x < y => loop(xs, yss, x :: acc)
    case (_, y :: ys) => loop(xss, ys, y :: acc)
    case (x :: xs, Nil) => loop(xs, Nil, x :: acc)
    case (Nil, Nil) => acc.reverse
  }

  loop(x, y, Nil)
}