Menu Close

Elemento ausente

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

   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,

   ausente [3,0,1]               ==  2
   ausente [1,2,0]               ==  3
   ausente (1+10^7:[0..10^7-1])  ==  10000000

Soluciones

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)

10 soluciones de “Elemento ausente

  1. fracruzam
    import Data.List
     
    ausente :: [Integer] -> Integer
    ausente xs = head $ (map fromIntegral [0..length xs])  xs
  2. juamorrom1
    import Data.List
     
    ausente :: [Integer] -> Integer
    ausente xs = aux (sort xs) [0..genericLength xs]
            where aux :: Eq a => [a] -> [a] -> a
                  aux [] (y:ys) = y
                  aux (x:xs) (y:ys) | x == y    = aux xs ys
                                    | otherwise = y
  3. manvermor
    import Data.List
     
    -- Versión alternativa a la de fracruzam sin usar fromIntegral ni map
     
    ausente :: [Integer] -> Integer
    ausente xs = head ([0..genericLength xs]  xs)
  4. erisan
    import Data.List
     
    ausente :: [Integer] -> Integer
    ausente xs = if xss `elem` xs then head [y | (x,y) <- zip (sort xs) [0..], x /= y] else xss
                where xss = genericLength xs
  5. abrdelrod
    import Data.List
     
    ausente :: [Integer] -> Integer
    ausente xs = (aux 0 . sort) xs
                 where aux n (y:ys) | y == n = aux (n+1) ys
                                    | otherwise = n
                       aux _ _ = genericLength xs
    • abrdelrod
      -- Una pequeña mejora:
      import Data.List
       
      ausente :: [Integer] -> Integer
      ausente = aux 0.sort
                   where aux n (y:ys) | y == n = aux (n+1) ys
                                      | otherwise = n
                         aux n _ = n
  6. erisan
    /* Esta es la definición por Maxima */ 
     
    ausente (xs) :=
      block ([yss:lreduce("+",makelist (k,k,1,length (xs))),
              pss:lreduce("+",xs)],
             yss-pss)$
  7. manpende

    import Data.List
    
    ausente :: (Enum a, Num a, Ord a) => [a] -> a
    ausente xs | p == [] = genericLength xs
               | otherwise = head p
                   where p = [y | (x,y) <- zip (sort xs)
                             [0..genericLength xs], x /= y]
    

  8. manpende
    import Data.List
     
    ausente :: (Enum a, Num a, Ord a) => [a] -> a
    ausente xs | p == [] = genericLength xs
               | otherwise = head p
                   where p = [y | (x,y) <- zip (sort xs)
                             [0..genericLength xs], x /= y]
  9. anaagusil
    -- Poco eficiente
    casiCompleta :: (Enum a, Num a, Ord a) => [a] -> Bool
    casiCompleta xs = length (nub (union xs [0..n])) == length xs + 1
                 where n = last (sort xs)
     
    ausente xs | casiCompleta xs = head ([0..(last (sort xs))]  xs)
               | otherwise       = head ([0..(last (sort xs) +1)]  xs)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.