Haskell - Selecció P91071


Statement
 

pdf   zip

thehtml

Implementeu una funció select :: Ord a => [a] -> Int -> a que, donada una llista d’elements xs i un enter k amb 1≤ klength xs, retorni l’element que es trobaria a la k-èsima posició de la llista ordenada.

Per exemple, en una llista amb n elements, per a k=1, cal retornar el mínim dels elements; per a k=n, cal retornar el màxim dels elements i per a k=n/2 cal retornar la mediana dels elements.

Ordenar tota la llista i indexar hauria de ser massa lent. Us suggerim utilitzar l’algorisme de mediana de medianes.

Public test cases
  • Input

    select [10,99,66,77,23,45,67] 3
    select [8,3,4,2,1,5,9,7,6] 1
    select [8,3,4,2,1,5,9,7,6] 2
    select [8,3,4,2,1,5,9,7,6] 5
    select [8,3,4,2,1,5,9,7,6] 8
    select [8,3,4,2,1,5,9,7,6] 9
    select [30,10,30,10,30,10] 2
    select ["mireia", "arnau", "jordi"] 2
    

    Output

    45
    1
    2
    5
    8
    9
    10
    "jordi"
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell