Sea xs una lista y n su longitud. Se dice que xs es casi completa si sus elementos son los números enteros entre 0 y n excepto uno. Por ejemplo, la lista [3,0,1] es casi completa.
Definir la función
|
1 |
ausente :: [Integer] -> Integer |
tal que (ausente xs) es el único entero (entre 0 y la longitud de xs) que no pertenece a la lista casi completa xs. Por ejemplo,
|
1 2 3 |
ausente [3,0,1] == 2 ausente [1,2,0] == 3 ausente (1+10^7:[0..10^7-1]) == 10000000 |
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import Data.List (foldl', genericLength) import Data.Set (fromList, notMember) -- 1ª definición ausente1 :: [Integer] -> Integer ausente1 xs = head [n | n <- [0..], n `notElem` xs] -- 2ª definición ausente2 :: [Integer] -> Integer ausente2 xs = head [n | n <- [0..], n `notMember` ys] where ys = fromList xs -- 3ª definición (lineal) ausente3 :: [Integer] -> Integer ausente3 xs = ((n * (n+1)) `div` 2) - sum xs where n = genericLength xs -- 4ª definición ausente4 :: [Integer] -> Integer ausente4 xs = ((n * (n+1)) `div` 2) - foldl' (+) 0 xs where n = genericLength xs -- Comparación de eficiencia -- ========================= -- λ> let n = 10^5 in ausente1 (n+1:[0..n-1]) -- 100000 -- (68.51 secs, 25,967,840 bytes) -- λ> let n = 10^5 in ausente2 (n+1:[0..n-1]) -- 100000 -- (0.12 secs, 123,488,144 bytes) -- λ> let n = 10^5 in ausente3 (n+1:[0..n-1]) -- 100000 -- (0.07 secs, 30,928,384 bytes) -- λ> let n = 10^5 in ausente4 (n+1:[0..n-1]) -- 100000 -- (0.02 secs, 23,039,904 bytes) -- -- λ> let n = 10^7 in ausente2 (n+1:[0..n-1]) -- 10000000 -- (14.32 secs, 15,358,509,280 bytes) -- λ> let n = 10^7 in ausente3 (n+1:[0..n-1]) -- 10000000 -- (5.57 secs, 2,670,214,936 bytes) -- λ> let n = 10^7 in ausente4 (n+1:[0..n-1]) -- 10000000 -- (3.36 secs, 2,074,919,184 bytes) |