Использование `quick-look` для поиска определенного элемента

Question

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

Моя задача состояла в том, чтобы написать алгоритм, который находит k:th наименьший элемент в последовательности, используя q uickselect. Это должно быть достаточно просто, но при выполнении некоторых тестов я врезался в стену. По какой-то причине, если я использую ввод (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 массива. Первый содержит непрерывную последовательность элементов, меньшую, чем сводный элемент, а второй содержит остальные.

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

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

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

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

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