Блог

Прежде всего, я хочу сказать, что это школьное задание, и я только ищу некоторые рекомендации.

Моей задачей было написать алгоритм, который находит k-й наименьший элемент в seq с помощью quickselect. Это должно быть достаточно просто, но при выполнении некоторых тестов я натыкаюсь на стену. По какой-то причине, если я использую ввод (List(1, 1, 1, 1), 1) , он переходит в бесконечный цикл.

Вот моя реализация:

   val rand = new scala.util.Random()

  def find(seq: Seq[Int], k: Int): Int = {
    require(0 <= k amp;amp; 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) 
  }
  

По какой-то причине (или потому, что я устал) Я не могу определить свою ошибку. Если бы кто-нибудь мог намекнуть мне, где я ошибаюсь, я был бы рад.

В основном вы зависите от этой строки — val (low, high) = a.partition(_ < a(pivot)) разбить массив на 2 массива. Первый содержит непрерывную последовательность элементов, меньших, чем сводный элемент, а второй содержит остальные.

Затем вы говорите, что если первый массив имеет длину k , это означает, что вы уже видели k элементы, меньшие, чем ваш сводный элемент. Это означает, что сводный элемент k 1 на самом деле является наименьшим, и вы фактически возвращаете k 1 наименьший элемент вместо th k . Это ваша первая ошибка.

Также… Большая проблема возникает, когда у вас есть все одинаковые элементы, потому что ваш первый массив всегда будет содержать 0 элементов.

Не только это … ваш код даст вам неправильный ответ для входных данных, где у вас есть повторяющиеся элементы среди k самых маленьких, например — (1, 3, 4, 1, 2) .

Решение заключается в том, что в последовательности (1, 1, 1, 1) 4 наименьшим элементом является 4 th 1 . Это означает, что вы должны использовать <= вместо < .

Также… Поскольку partition функция не будет разбивать массив до тех пор, пока ваше boolean условие не станет ложным, вы не можете использовать partition для достижения этого разделения массива. вам придется написать разделение самостоятельно.