Verwenden von `Quick-Look`, um bestimmte Element zu finden

Question

Zunächst möchte ich sagen, dass dies eine Schulaufgabe ist und ich nur für eine Anleitung suche.

Meine Aufgabe war es, einen Algorithmus zu schreiben, der das k: kleinste Element in einem Seq mit Quickselect findet. Das sollte einfach sein, aber wenn ich ein paar Tests mache, treffe ich eine Wand. Aus irgendeinem Grund, wenn ich den Eingang (List(1, 1, 1, 1), 1) verwende, geht es in die Endlosschleife.

Hier ist meine Implementierung:

val rand = new scala.util.Random() 

    def find(seq: Seq[Int], k: Int): Int = { 
    require(0 <= k && k < seq.length)   
    val a: Array[Int] = seq.toArray[Int]  // Can't modify the argument sequence 

    val pivot = rand.nextInt(a.length) 
    val (low, high) = a.partition(_ < a(pivot)) 
    if (low.length == k) a(pivot) 
    else if (low.length < k) find(high, k - low.length) 
    else find(low, k) 
    } 

Aus irgendeinem Grund (oder weil ich müde bin) Ich kann nicht mein Fehler erkennen. Wenn mir jemand sagen könnte, wo ich falsch liege, würde ich mich freuen.

Answer 1

Grundsätzlich sind Sie abhängig von dieser Zeile - val (low, high) = a.partition(_ < a(pivot)), um das Array in 2 Arrays zu teilen. Der erste enthält die kontinuierliche Folge von Elementen, die kleiner als das Pivot-Element sind, und der zweite enthält den Rest.

Dann sagen Sie, dass, wenn das erste Array die Länge k hat, das bedeutet, Sie haben bereits k Elemente kleiner als Ihre Pivot-Element gesehen. Was bedeutet, Pivot-Element ist tatsächlich k+1 Th kleinste und Sie sind tatsächlich zurück k+1 Th kleinste Element anstelle von k th. Das ist dein erster Fehler.

Auch ... Ein größeres Problem tritt auf, wenn Sie alle Elemente haben, die identisch sind, weil Ihr erstes Array immer 0 Elemente hat.

Nicht nur das ... Ihr Code wird Ihnen falsche Antwort für Eingänge geben, wo Sie sich wiederholende Elemente zwischen k kleinsten wie - (1, 3, 4, 1, 2). Die Lösung liegt darin, dass in der Reihenfolge (1, 1, 1, 1) das kleinste Element 4 ist. Das heißt, Sie müssen <= anstelle von < verwenden.

Auch ... Da die Funktion partition das Array nicht aufteilt, bis Ihre boolean Bedingung falsch ist, können Sie die Partition nicht verwenden, um diese Array-Aufteilung zu erreichen. Du wirst die Spaltung selbst schreiben müssen.