0

まず第一に、これは学校の課題であり、指導を求めているだけです。

私の仕事は、quickselect を使用して、seq 内の 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) 
  }

なんらかの理由で (または疲れているため)、間違いを見つけることができません。誰かが私がどこで間違っているかを教えてくれたら、私は喜んでいます.

4

1 に答える 1

1

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

次に、最初の配列に長さがある場合は、ピボット要素よりも小さい要素kが既に見られていることを意味します。kつまり、pivot-element は実際にはth 最小であり、実際には th ではなく th 最小要素をk+1返しています。これはあなたの最初の間違いです。k+1k

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

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

解決策は、シーケンス (1, 1, 1, 1) で4th 番目に小さい要素が th4であるという観察にあります1。<=の代わりに使用する必要があることを意味します<。

また...条件がfalseにpartitionなるまで関数は配列を分割しbooleanないため、この配列分割を実現するためにパーティションを使用することはできません。分割は自分で書く必要があります。

于 2016-09-29T12:00:10.260 に答える