1

Fazer uma função chamada faltante que, dada uma lista com N − 1 inteiros numerados de 1 a N, descubra qual número inteiro deste intervalo está faltando. Não estou conseguindo achar um código que englobe qualquer lista de inteiros.

def faltante(L: List[int]):
''' teste '''
    posicao = 0
    while L[posicao] < len(L):
        if posicao+1 == L[posicao]:
            posicao = posicao + 1
        break
    return posicao+1

Saída

print(faltante([1, 2, 3, 5, 6, 7, 8]))

retorna 2, esperava 4

4
  • Marco, boa tarde! Insira no seu código um exemplo de uma lista que deseja testar e o resultado esperado. Abraços! Commented 8/10/2020 às 21:02
  • Os números sempre estarão em ordem crescente?
    – hkotsubo
    Commented 8/10/2020 às 21:43
  • Sim. Estarão em ordem crescente
    – Marco Raad
    Commented 8/10/2020 às 21:51
  • Vai faltar apenas um número ou podem faltar mais de um número na lista? Commented 9/10/2020 às 1:00

4 Respostas 4

5

Você pode comparar se o próximo elemento é a soma do elemento atual + 1, caso seja diferente adicionamos o item atual + 1 (que deveria ser o valor real) a lista, que está dentro da função, e ao final da execução retornamos essa lista:

def faltante(lista):
    lst_return = []    
    
    for i in range(len(lista) - 1): 
        if lista[i + 1] != lista[i] + 1 :
            lst_return.append(lista[i] + 1)
            
    return lst_return

Saída:

print(f'Números faltantes: {faltante([1,2,3,5,6,7,8,10])}')
Números faltantes: [4, 9]

Uma alternativa para listas como [1, 5, 7, 9]:

é utilizar o range:

lst_return.append(list(range(lista[i] + 1, lista[i + 1])))

Saída:

print(f'Números faltantes: {faltante([1, 5, 7, 9])}')
Números faltantes: [[2, 3, 4], [6], [8]]

Uma forma mais geral:

def faltante(lista):
    lst_return = []    
        
    if lista[0] != 0:
        lst_return.append(list(range(0, lista[0])))
        
    for i in range(len(lista) - 1):    
        if lista[i + 1] != lista[i] + 1 :
            lst_return.append(list(range(lista[i] + 1, lista[i + 1])))
            
    return lst_return

Saída:

print(f'Números faltantes: {faltante([5, 7, 9])}')
Números faltantes: [[0, 1, 2, 3, 4], [6], [8]]
0
4

Para verificarmos TODOS os números que porventura esteja faltando em uma lista qualquer, basta utilizarmos o código abaixo.

NOTA: Este código pode englobar quaisquer listas de inteiros - crescente, decrescente, alternada, com valores positivos, com valores negativos, com valor nulo e com valores positivos, negativos e nulos.

def faltante(lis):
    menor = min(lis)
    maior = max(lis)
    faltando = list()
    for c in range(menor, maior + 1):
        if c not in lis:
            faltando.append(c)
    return faltando


numeros = list(map(int, input('Digite alguns números: ').split()))

print(f'Os números faltantes são:\n{faltante(numeros)}')

Observe que quando executamos este código recebemos a seguinte mensagem: Digite alguns números: . Neste momento devemos digitar todos os número que desejarmos, na mesma linha, separados por um só espaço e pressionar enter.

Após a inserção dos valores, os mesmo serão montados na lista números e, em seguida, a mesma é passada como parâmetro para a função faltante. Chegando lá, é calculado o menor e maior valor da referida lista. Posteriormente, o for percorrerá o range(menor, maior + 1) e, com o auxílio do bloco if, é verificado se cada elemento da respectiva interação não pertence à lista - parâmetro lis. Caso o respectivo elemento não pertença à lista, o mesmo é adicionado à lista faltando.

Depois destas operações a lista de números faltantes é exibida.

Vamos testa a execução do código?

Exemplo 1:

Vamos digitar os valores...

1 2 3 5 6 7 8 10

A saída será:

[4, 9]

Exemplo 2:

Vamos digitar os valores...

1 5 7 9

A saída será:

[2, 3, 4, 6, 8]

Exemplo 3:

Vamos digitar os valores:

1 12 13 15 17 20

A saída será:

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 16, 18, 19]

Observe que em ambos exemplos, o código foi capaz de verificar e exibir TODOS os valores FALTANTES em uma só lista e em ordem crescente.

Outra coisa, ao calcular o menor e o maior valor da lista já habilito a função para trabalhar com valores que também não estejão em ordem - crescente ou decrescente.

Exemplo 4:

Vamos digitar os valores:

12 9 2 5 18

A saída será:

[3, 4, 6, 7, 8, 10, 11, 13, 14, 15, 16, 17]

Exemplo 5:

Vamos digita os valores:

4 20

A saída será:

[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Exemplo 6:

Vamos digitar os valores:

-10 -3 6 12

A saída será:

[-9, -8, -7, -6, -5, -4, -2, -1, 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11]

Resumo

Este código é capaz de identificar e exibir todos os valores faltantes de uma lista de números inteiros - positivos, negativos e nulos - independentemente da ordem - crescente, decrescente ou alternada - que os valores se apresentarem.

3

Como parece ser um exercício, "provavelmente querem" que você faça com um loop simples. Mas apenas para deixar registrado, você pode resolver usando set:

def faltante(numeros):
    # intervalo contendo todos os números possíveis (baseado na lista de números)
    # vai do menor valor existente da lista até o maior
    intervalo = range(min(numeros), max(numeros) + 1)
    return list(set(intervalo) - set(numeros))

Ou, juntando tudo em uma linha:

def faltante(numeros):
    return list(set(range(min(numeros), max(numeros) + 1)) - set(numeros))

A ideia é gerar 2 set's:

  • o primeiro set contém todos os números possíveis. Estou considerando que o intervalo vai do menor número existente na lista até o maior número existente na lista. Isso não cobre os casos em que o primeiro ou o último estão faltando. Por exemplo, se a lista for [2, 5, 8], o número 1 está faltando? Ou eu considero apenas os números a partir do 2? Estou considerando que é o segundo caso (que também é o que as outras respostas fizeram).

    Aliás, também existe a limitação de não considerar o caso em que o maior número está faltando: se a lista for [1,2,3], o 4 está faltando? Esta solução - e as outras respostas também - consideram que não (se bem que, em um caso mais geral como [2, 5, 9], como saber se o 10 está faltando ou não? Nesse caso acho melhor considerar que o 9 é o limite máximo - mas logo abaixo deixo uma alternativa para resolver isso).

  • o segundo set contém apenas os números da lista.

Subtraindo os set's, temos os números faltantes, e eu transformo o set resultante em lista (embora não seja necessário, se você apenas quiser os números, tanto faz a estrutura em que eles são retornados).

Vale lembrar que um set não garante a ordem dos elementos, então a lista nem sempre retornará os números em ordem (mas se quiser, pode usar sorted para retornar a lista ordenada):

def faltante(numeros):
    return sorted(list(set(range(min(numeros), max(numeros) + 1)) - set(numeros)))

Sobre o problema do limite mínimo e máximo, você ainda pode fazer desta forma:

def faltante(numeros, minimo = None, maximo = None):
    if minimo is None:
        minimo = min(numeros)
    if maximo is None:
        maximo = max(numeros)
    intervalo = range(minimo, maximo + 1)
    return sorted(list(set(intervalo) - set(numeros)))

print(faltante([1, 2, 3, 5])) # 4

# falta o 5
print(faltante([1, 2, 3, 4], maximo=5))

# falta o 1
print(faltante([2, 3, 4, 5], minimo=1)) # 1

# falta o -1, 0 e 1, além do 6 e 7
print(faltante([2, 3, 4, 5], minimo=-1, maximo=7)) # [-1, 0, 1, 6, 7]

Assim, eu posso parametrizar os valores que são considerados. Por exemplo, em uma lista como [1,2,3], eu posso indicar que o 4 está faltando passando o parâmetro maximo=4 - e se eu não passar nenhum valor, ele usa a lógica anterior, de pegar o menor e maior valor da lista como os limites.

Claro que esse algoritmo não é lá muito eficiente, já que chamar max e min separadamente percorre a lista 2 vezes, e a própria criação de set's (e a ordenação da lista ao final) também têm um custo adicional.


Mas no caso específico do exercício (sempre são números de 1 a N, somente um deles com certeza está faltando e eles sempre estarão em ordem crescente), dá para fazer assim:

def faltante(numeros):
    if numeros[0] != 1: # ver se o 1 está faltando
        return 1
    for i, n in enumerate(numeros):
        if i == len(numeros) - 1 or n + 1 != numeros[i + 1]:
            return n + 1

print(faltante([1, 2, 3, 5])) # 4

# falta o 5
print(faltante([1, 2, 3, 4])) # 5

# falta o 1
print(faltante([2, 3, 4, 5])) # 1

Eu uso enumerate para iterar pelos elementos e seus respectivos índices. Depois, basta ver se eu cheguei no último elemento (para o caso do último estar faltando), ou se o elemento seguinte não é igual ao atual + 1. Em ambos os casos o elemento que falta é o atual + 1.

Só que antes do loop tem que incluir uma verificação especial para o caso do 1 estar faltando.

Mas se a ideia é ter uma solução mais geral, basta usar set ou algum dos algoritmos das outras respostas.

4
  • 1
    Posso ter analisado errado (sono), mas na solução com conjuntos é arriscado utilizar max(numeros) + 1 como limite máximo pois como a lista é numerada de 1 a N, se for o próprio N que não está na lista a sua solução iria considerar apenas até N-1, não?
    – Woss
    Commented 9/10/2020 às 11:21
  • @Woss Sim, existe essa limitação. Acho que não tem muito jeito. Se a ideia é considerar somente o caso do exercício (sempre números de 1 a N, somente um está faltando), o loop me parece a melhor opção. Mas em um caso genérico como [2, 7, 9], não tem como saber qual o limite máximo (é o 9? algum outro número maior?) De qq forma, adicionei umas observações sobre isso, obrigado!
    – hkotsubo
    Commented 9/10/2020 às 11:27
  • 1
    Poderia receber N por parâmetro também, já que ele parametriza o problema xD
    – Woss
    Commented 9/10/2020 às 11:28
  • @Woss Mas é claro! Acho que estou com sono também, devia ter pensando nisso antes. Atualizei a resposta, obrigado mais uma vez :-)
    – hkotsubo
    Commented 9/10/2020 às 11:36
2

Veja um programa baseado no seu, com algumas alterações:

def faltantes(L):
    if L:                             # se L tem conteudo...
        elemento = L[0]               # ...pego o primeiro elemento
        posicao = 1                   # e aponto para o 2o elemento
        while posicao < len(L):       # enquanto posicao nao chegar ao fim de L
            # se elemento *não* for antecessor a L na posicao atual...
            if (elemento + 1) < L[posicao]: 
                elemento += 1         # incremento elemento...
                yield elemento        # ... e devolvo um gerador com este elemento
            else:                     # senao...
                elemento = L[posicao] # ...tomo o elemento atual e
                posicao += 1          # ando para a proxima posicao de L
    
# programa
print('Primeira lista')
for i in faltantes([1,2,3, 5,6,7,8]):
  print(i)

print('Segunda lista')
for i in faltantes([]):
  print(i)

print('Terceira lista')
for i in faltantes([2, 4,5, 7, 9]):
  print(i)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .