Menu Close

Elemento ausente

José A. Alonso,

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)
Medio
, , , , , , , , ,

10 soluciones de “Elemento ausente”

  1. Responder
    fracruzam 
    import Data.List
 
ausente :: [Integer] -> Integer
ausente xs = head $ (map fromIntegral [0..length xs])  xs
  2. Responder
    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. Responder
    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. Responder
    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. Responder
    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
    • Responder
      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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.