0

首先，我想说这是一个学校作业，我只是寻求一些指导。

我的任务是编写一个算法，使用快速选择找到序列中的第 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 个数组。第一个包含小于枢轴元素的连续元素序列，第二个包含其余元素。

然后你说如果第一个数组有长度k，这意味着你已经看到k比你的枢轴元素更小的元素。这意味着枢轴元素实际上是k+1最小的，并且您实际上返回的是k+1最小的元素而不是kth。这是你的第一个错误。

另外......当您拥有所有相同的元素时会出现更大的问题，因为您的第一个数组将始终有 0 个元素。

不仅如此......你的代码会给你错误的答案，因为你在k最小的元素中有重复元素，比如 - (1, 3, 4, 1, 2)。

解决方案在于观察到，在序列 (1, 1, 1, 1) 中，4第 th 最小的元素是4th 1。这意味着您必须使用<=而不是<.

另外...由于该partition函数在您的条件为假之前不会拆分数组boolean，因此您不能使用分区来实现此数组拆分。您将不得不自己编写拆分。

于 2016-09-29T12:00:10.260 回答