在排序后的数组中找到一对总和为X的整数的函数式方法 [英] Functional way to find a pair of integers, which sum to X, in a sorted array
问题描述
这是我以前的问题。
假设我想在给定的排序数组中找到一对整数,它们的和等于给定数字 x
。众所周知的一次通过解决方案如下所示:
This is a follow-up to my previous question.
Suppose I want to find a pair of integers, which sum to a given number x
, in a given sorted array. The well-known "one pass" solution looks like that:
def pair(a: Array[Int], target: Int): Option[(Int, Int)] = {
var l = 0
var r = a.length - 1
var result: Option[(Int, Int)] = None
while (l < r && result.isEmpty) {
(a(l), a(r)) match {
case (x, y) if x + y == target => result = Some(x, y)
case (x, y) if x + y < target => l = l + 1
case (x, y) if x + y > target => r = r - 1
}
}
result
}
你如何建议在没有任何可变状态的情况下编写函数?
我想我可以用
您可以推荐一个非递归版本吗?
How would you suggest write functionally without any mutable state ?
I guess I can write a recursive version with Stream
(lazy list in Scala)
Could you suggest a non-recursive version ?
推荐答案
这是一个相当简单的版本。它创建一个 Stream <
Vectors
,它删除每次迭代中的第一个或最后一个元素。然后我们限制无限 Stream
(-1,所以你不能在自己中添加一个数字),然后 map
它转换为输出格式并检查目标情况。
Here's a fairly straightforward version. It creates a Stream
of Vectors
that removes the first or last element on each iteration. Then we limit the size of the otherwise infinite Stream
(-1 so you can't add a number with itself), then map
it into the output format and check for the target condition.
def findSum(a: Vector[Int], target: Int): Option[(Int, Int)] = {
def stream = Stream.iterate(a){
xs => if (xs.head + xs.last > target) xs.init else xs.tail
}
stream.take (a.size - 1)
.map {xs => (xs.head, xs.last)}
.find {case (x,y) => x + y == target}
}
隐藏了很多宝石Scala的集合的伴侣对象,如 Stream.iterate
。我强烈建议检查出来。了解它们可以大大简化这样的问题。
There are a lot of gems hidden in the companion objects of Scala's collections, like Stream.iterate
. I highly recommend checking them out. Knowing about them can greatly simplify a problem like this.
这篇关于在排序后的数组中找到一对总和为X的整数的函数式方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!