Использование `quick-look`, чтобы найти определенный элемент

Question

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

Моя задача - написать алгоритм, который найдет k: th наименьший элемент в 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 && 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 th 1. Это означает, что вы должны использовать <= вместо <.

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