Utiliser `quick-look` pour trouver certains éléments

Question

Tout d'abord, je veux dire que c'est une tâche d'école et je ne cherche que des conseils.

Ma tâche consistait à écrire un algorithme qui trouve le k: le plus petit élément dans un seq en utilisant quickselect. Cela devrait être assez facile mais quand j'effectue des tests, je frappe un mur. Pour une raison quelconque, si j'utilise l'entrée (List(1, 1, 1, 1), 1), elle passe en boucle infinie.

Voici mon implémentation:

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) 
    } 

Pour une raison quelconque (ou parce que je suis fatigué) Je ne peux pas repérer mon erreur. Si quelqu'un pouvait m'indiquer où je me trompe, je serais heureux.

Answer 1

Fondamentalement, vous dépendez de cette ligne - val (low, high) = a.partition(_ < a(pivot)) pour diviser la baie en 2 rangées. La première contient la séquence continue d'éléments plus petits que l'élément pivot et la seconde contient le reste.

Ensuite, vous dites que si le premier tableau a la longueur k cela signifie que vous avez déjà vu k éléments plus petits que votre élément-pivot. Ce qui signifie que l'élément pivot est en fait le plus petit et que vous renvoyez k+1 au plus petit élément au lieu de k e. C'est ta première erreur.

Aussi ... Un problème plus important se produit lorsque vous avez tous les éléments qui sont identiques parce que votre premier tableau aura toujours 0 éléments.

Non seulement cela ... votre code vous donnera une mauvaise réponse pour les entrées où vous avez des éléments répétitifs parmi k les plus petits comme - (1, 3, 4, 1, 2).

La solution réside dans l'observation que dans la séquence (1, 1, 1, 1) 4 le plus petit élément est le 4 e 1. Cela signifie que vous devez utiliser <= au lieu de <.

Aussi ... Puisque la fonction partition ne divisera pas le tableau jusqu'à ce que votre condition boolean soit fausse, vous ne pouvez pas utiliser la partition pour réaliser cette division de tableau. vous devrez écrire la scission vous-même.