Haskell - Selecció P91071


Statement
 

pdf   zip

html

Implementeu una funció select :: Ord a => [a] -> Int -> a que, donada una llista d’elements xs i un enter k amb 1≤ k≤ length 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