クイックルックを使用して特定の要素を見つける

Question

まず、これは学校の割り当てであり、私はいくつかのガイダンスのみを求めています。

私の仕事は、quickselectを使ってse：にk番目の最小要素を見つけるアルゴリズムを書くことでした。これは十分に簡単なはずですが、いくつかのテストを実行するときに壁に当たった。何らかの理由で、私が入力(List(1, 1, 1, 1), 1)を使用すると、無限ループに入ります。ここで

は私の実装です：何らかの理由

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) 
    } 

（または私は疲れているので）、私は私のミスを見つけることができません。誰かが私が間違っているところを私に示唆することができたら、私は喜ぶだろう。

Answer 1

基本的には、この行に依存しています - val (low, high) = a.partition(_ < a(pivot))は、配列を2つの配列に分割します。最初の要素はピボット要素よりも小さい要素の連続シーケンスを含み、2番目の要素は残りを含みます。

次に、最初の配列の長さがkであれば、すでにkの要素がピボット要素より小さくなっていることがわかります。つまり、ピボット要素は実際にはk+1であり、実際にはk番の代わりにk+1番の最小要素を返しています。これがあなたの最初の間違いです。

また、最初の配列には常に0個の要素があるため、同じ要素がすべてある場合に大きな問題が発生します。

だけでなく、あなたのコードは、(1, 3, 4, 1, 2)のような最小のものkの中の繰り返し要素を持つ入力に対して間違った答えを与えるでしょう。

この解決策は、シーケンス（1,1,1）において最小の要素が4 thであるというオーバーレンにある。つまり、<の代わりに<=を使用する必要があります。

また、boolean条件がfalseになるまでpartition関数が配列を分割しないため、この配列分割を達成するためにpartitionを使用することはできません。自分で分割しなければなりません。