Functional „Find-Paare, die zu X aufaddieren“

Question

mit linearer Zeitkomplexität ich die „finden Paare, die zu X aufaddieren“ umzusetzen versuchen funktionell mit linearer Zeitkomplexität, für die ich habe folgend:

def pairs(nums: List[Int], sum: Int): List[(Int, Int)] = { 

    def pairsR(nums: List[Int], sum: Int, start: Int, end: Int, acc: List[(Int, Int)]): List[(Int, Int)] = { 

    val newAcc = nums(start) + nums(end) match { 
     case n if n == sum => ((nums(start), nums(end)) :: acc, start + 1, end - 1) 
     case n if n < sum => (acc, start + 1, end) 
     case n if n > sum => (acc, start, end - 1) 
    } 

    if(start < end) pairsR(nums, sum, newAcc._2, newAcc._3, newAcc._1) 
    else newAcc._1 
    } 

    pairsR(nums, sum, 0, nums.length - 1, List()) 
}  

Das würde funktionieren, wenn ich versuchen würde, nach dem ersten Paar zu suchen, das zu X addiert (vorausgesetzt, dass ich nach dem ersten Auftreten zurückkomme). Aber weil ich versuche, alle Paare zu finden, erhalte ich einige Duplikate, wie hier zu sehen ist: (Beachten Sie, dass es in der Liste nur eine einzige 5 gibt, aber da die Zeiger zur selben Zeit auf 5 ankommen, rate ich sie zweimal)

pairs(List(1,2,3,4,5,6,7,8,9), 10) should equalTo (List((1, 9), (2, 8), (3, 7), (4, 6))) 

Doch bekomme ich folgende Fehler an:

List ((5,5), (4,6), (3,7), (2,8), (1,9)) nicht gleich List ((1,9), (2,8), (3,7), (4,6))

dieser Algorithmus ist einfach nicht möglich zu erreichen, in lineare Zeit, wenn Sie ALLE Paare suchen (und nicht nur die erste)? Ich weiß, dass es mit einem HashSet möglich ist, aber ich wollte wissen, ob Sie den "Zeiger" -Ansatz verwenden könnten. Hier

Answer 1

ist eine aktualisierte Version des Codes:

def pairs(nums: List[Int], sum: Int): List[(Int, Int)] = { 
    val numsArr = nums.toArray 

    def pairsR(start: Int, end: Int, acc: List[(Int, Int)]): List[(Int, Int)] = 
    numsArr(start) + numsArr(end) match { 
     case _ if start >= end => acc.reverse 
     case `sum` => pairsR(start + 1, end - 1, (numsArr(start), numsArr(end)) :: acc) 
     case n if n < sum => pairsR(start + 1, end, acc) 
     case n if n > sum => pairsR(start, end - 1, acc) 
    } 

    pairsR(0, numsArr.length - 1, Nil) 
} 

Test:

pairs(1 to 9 toList, 10) 

Ergebnis:

res0: List[(Int, Int)] = List((1,9), (2,8), (3,7), (4,6)) 

Einige Anmerkungen:

1. Wenn sich die Zeiger start und end irgendwo in der Mitte des Arrays schneiden, ist es an der Zeit, die Rekursion zu beenden und acc zurückzugeben. Diese Bedingung muss zuerst gehen, so dass Sie keine generische Logik anwenden
2. Wie Sie Ergebnisse an die acc vorgeben, ist acc in umgekehrter Reihenfolge am Ende, so dass es sinnvoll ist, reverse es vor der Rückkehr.
3. Keine Notwendigkeit statische Parameter, wie nums und sum als Argumente der inneren rekursive Funktion
4. Da die Menschen in den Kommentaren vorgeschlagen hinzuzufügen, wenn Sie mit konstanter Zeit indiziert Zugang, Ihre Wahl Array ist schreibgeschützt Sammlung benötigen. Vector wird auch funktionieren, aber es ist langsamer

Als Randbemerkung, können aktuelle Implementierung zu falschen Ergebnissen führen, wenn Sie doppelte Elemente in Ihrer Eingabeliste haben:

pairs(List(1,1,1,2,2), 3) 

Ergebnis:

res1: List[(Int, Int)] = List((1,2), (1,2)) 

Der einfachste Weg, dies zu beheben, ist die Vorverarbeitung der Eingangsliste, um doppelte Elemente zu entfernen. Dies führt dazu, dass das Ergebnis nur bestimmte Paare enthält. Wenn Sie jedoch alle Paare mit Elementen desselben Werts, aber unterschiedlichen Indexes einbeziehen möchten, ist dies nicht in linearer Zeit möglich. Betrachten Sie ein Beispiel, wenn Sie N Elemente mit X-Wert haben und alle Summen von 2X finden möchten.Die Länge des Ergebnisses ist N).

Auch dieser Algorithmus erfordert Eingabedaten sortiert werden. Es gibt eine einfache Änderung an dem Algorithmus, damit er mit unsortierten Daten arbeitet (unter Verwendung von counting sort).