Mayores que la mitad
Definir la función
|
1 |
mayoresMitad :: Ord a => [a] -> [a] |
tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,
|
1 2 3 4 |
sort (mayoresMitad [1,6,3,4]) == [4,6] sort (mayoresMitad [1,6,3,4,7]) == [4,6,7] sort (mayoresMitad [1,6,3,4,2]) == [3,4,6] length (mayoresMitad3 [1..10^6]) == 500000 |
Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import Data.List (sort) -- 1ª solución: mayoresMitad1 :: Ord a => [a] -> [a] mayoresMitad1 xs = [x | x <- xs , length (filter (<=x) xs) > k] where k = length xs `div` 2 -- 2ª solución mayoresMitad2 :: Ord a => [a] -> [a] mayoresMitad2 xs = aux xs where aux [] = [] aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys | otherwise = aux ys k = length xs `div` 2 -- 3ª solución mayoresMitad3 :: Ord a => [a] -> [a] mayoresMitad3 xs = drop k (sort xs) where k = length xs `div` 2 -- Comprobación de eficiencia -- λ> length (mayoresMitad1 [1..4*10^3]) -- 2000 -- (3.79 secs, 442,631,712 bytes) -- λ> length (mayoresMitad2 [1..4*10^3]) -- 2000 -- (11.82 secs, 1,463,762,192 bytes) -- λ> length (mayoresMitad3 [1..4*10^3]) -- 2000 -- (0.02 secs, 0 bytes) |