在排序後的數組中找到一對整數對的整數的函數式方法

Question

這是我以前的question的後續。 假設我想在給定的排序數組中找到一對整數，它們的和爲給定數字x。衆所周知的「一次通過」解決方案看起來像這樣：

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 
} 

你會如何建議寫功能沒有任何可變狀態？
我想我可以寫一個遞歸版本Stream（斯卡拉的懶惰列表） 你可以建議一個非遞歸版本嗎？

Answer 1

這是一個相當簡單的版本。它創建一個Stream的Vectors，刪除每次迭代中的第一個或最後一個元素。然後我們限制否則無限的Stream（-1，所以你不能自己添加一個數字）的大小，然後map它進入輸出格式並檢查目標條件。

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寶石。我強烈建議檢查出來。瞭解它們可以大大簡化這樣的問題。

Answer 2

下面是不使用索引（我儘量避免，除非有與他們的價值的重要計算）版本：

def findPair2(x: Int, a: Array[Int]): Option[(Int, Int)] = { 
    def findPairLoop(x: Int, l: Array[Int], r: Array[Int]): Option[(Int, Int)] = { 
     if (l.head >= r.last) None 
     else if (l.head + r.last == x) Some((l.head, r.last)) 
     else if (l.head + r.last > x) findPairLoop(x, l, r.init) 
     else findPairLoop(x, l.tail, r) 
    } 
    findPairLoop(x, a, a) 
} 

這是遞歸的，但並不需要流。 tail和init是O（N）的數組，但如果我們用列表和扭轉r收集，以避免init和last的O（N）的版本可以做到

def findPairInOrderN(x: Int, a: Array[Int]): Option[(Int, Int)] = { 
    def findPairLoop(x: Int, l: List[Int], r: List[Int]): Option[(Int, Int)] = { 
     if (l.head >= r.head) None 
     else if (l.head + r.head == x) Some((l.head, r.head)) 
     else if (l.head + r.head > x) findPairLoop(x, l, r.tail) 
     else findPairLoop(x, l.tail, r) 
    } 
    val l = a.toList 
    findPairLoop(x, l, l.reverse) 
} 

如果我們不關心單通過（或效率一般:)）這是一個內襯

(for (m <-a ; n <- a if m + n == x) yield (m,n)).headOption 

展開到這flatmap /地圖，然後用collectFirst爲我們提供了這一點，這是相當整潔和更優化的（但仍然不是爲O（n）） - 它停在第一對正確的位置，但是做了更多的工作而不是必要的。

a.collectFirst{case m => a.collectFirst{case n if n+m == x => (m,n)}}.get 

Answer 3

沒有遞歸和沒有可變狀態它可以變得非常醜陋。這裏是我的嘗試：

def f(l: List[Int], x: Int): Option[(Int, Int)] = { 
    l.foldLeft(l.reverse) { 
    (list, first) => 
     list.headOption.map { 
     last => 
      first + last match { 
      case `x` => return Some(first, last) 
      case sum if sum < x => list 
      case sum if sum > x => 
       val innerList = list.dropWhile(_ + first > x) 
       innerList.headOption.collect { 
       case r if r + first == x => return Some(first, r) 
       }.getOrElse { 
       innerList 
       } 
      } 
     }.getOrElse { 
     return None 
     } 
    } 
    None 
} 

例子：

scala> f(List(1, 2, 3, 4, 5), 3) 
res33: Option[(Int, Int)] = Some((1,2)) 

scala> f(List(1, 2, 3, 4, 5), 9) 
res34: Option[(Int, Int)] = Some((4,5)) 

scala> f(List(1, 2, 3, 4, 5), 12) 
res36: Option[(Int, Int)] = None 

在一開始.reverse加上foldLeft與回報時，結果發現使這一O(2n)。

Answer 4

這是一個內襯

[ (x, y) | x <- array, y <- array, x+y == n ] 

它甚至在未排序的名單。

但是，如果您想利用排序功能，只需對數組中的每個x進行二進制搜索即可，而不是遍歷數組。