0

O problema é fazer uma função que receba uma lista, e retorne True caso algum dos elementos se repitam ou False caso o contrário, sem modificar a lista original. Fiz um algoritmo, porém está sempre dando o mesmo resultado:

def verificar_lista(lista):
    itens = lista
    for i in range(len(itens)):
        if itens[i] not in itens:
            return False
        else:
            return True
    
        

print(verificar_lista([1, 9, 2, 4, 3, 3, 2]))
print(verificar_lista([1, 2, 3, 4, 5, 6, 7]))
1
  • 1
    Você está percorrendo os valores da lista e literalmente verificando se eles estão na lista... sempre estarão, por isso o retorno sempre é True.
    – Woss
    14/12/2020 às 20:13

3 Respostas 3

2
def verificar_lista(lista):
    itens = lista
    for i in range(len(itens)):
        if itens[i] not in itens:
            return False
        else:
            return True

Fazendo o teste de mesa é facilmente mostrado que o que o seu código faz é:

  • Se o primeiro elemento da lista não está na lista, retorna falso;
  • Caso contrário, retorna verdadeiro.

A questão é que sempre o primeiro elemento da lista estará na lista e, assim, sempre o retorno será True.

Como a ideia é verificar duplicados, você precisa verificar se aquele número está também no restante da lista, ignorado ele mesmo. No Python você pode fazer isso usando o slice:

def verificar_lista(lista):
    for posicao, numero in enumerate(lista):
        if numero in lista[posicao+1:]:
            return True
    else:
        return False
2

Há um erro conceitual no seu algoritmo:

1: def verificar_lista(lista):
2:     itens = lista
3:     for i in range(len(itens)):
4:         if itens[i] not in itens:
5:             return False
6:         else:
7:             return True

Veja, na linha 3, que você está percorrendo por cada elemento da lista e, para cada um deles (linha 4 agora) você verifica se o item está presente na lista.

Mas pense. Ora, se estou iterando sobre um item da lista, ele há de nela se encontrar. Então essa condição não faz o menor sentido (sempre será falsa, uma vez que o item sempre estará na lista). Portanto, a função em questão sempre retornará True.


Como o enunciado não pede para que especificamente seja retornado o(s) elemento(s) que se repete(m), você pode utilizar o set para resolver esse problema de forma simples. Como é uma estrutura de dados que não aceita valores repetidos, o que você pode fazer é, a partir da lista original, criar um novo conjunto e verificar se o número de elementos são iguais.

Se forem iguais, você pode afirmar que não existem elementos duplicados na lista. Caso contrário, um (ou mais) dos elementos foi removido automaticamente por serem duplicados. Aí você sabe que há elementos repetidos.

Veja:

def verificar_lista(lista):
    elementos = set(lista)

    if (len(elementos) == len(lista)):
        return False  # Não há elementos repetidos

    return True  # Há elementos repetido.


print(verificar_lista([1, 9, 2, 4, 3, 3, 2]))  # True (3 se repete)
print(verificar_lista([1, 2, 3, 4, 5, 6, 7]))  # False

Removendo o if (desnecessário no código acima já que a função é resultado de uma avaliação de comparação simples):

def verificar_lista(lista):
    return len(set(lista)) != len(lista)


print(verificar_lista([1, 9, 2, 4, 3, 3, 2]))  # True (3 se repete)
print(verificar_lista([1, 2, 3, 4, 5, 6, 7]))  # False

A vantagem de utilizar o set para esse tipo de situação é que é bem mais eficiente que utilizar o operador in. Veja aqui que a complexidade do in é linear e, ao aninhá-lo dentro de um outro for, você acaba por criar algoritmo perto de complexidade quadrática.

Se o enunciado fosse um pouco mais complexo, daria para usar um Counter também. Mas nesse caso creio ser meio overkill.

2
2

As outras respostas já explicaram o problema do seu algoritmo, mas só para dar mais algumas opções de solução, uma alternativa é usar um Counter:

from collections import Counter

def verificar_lista(lista):
    return len(Counter(lista)) != len(lista)

O Counter é um dicionário que contém, para cada elemento da lista, a quantidade de vezes que ele ocorre. Então se a quantidade de chaves dele for igual ao tamanho da lista, é porque nenhum elemento se repete. Mas nesse caso específico eu confesso que acho um exagero usar Counter (veremos o porquê no final), e só seria recomendado se você precisasse de fato das quantidades de vezes que cada elemento ocorre.


Outra opção é usar set e ir aos poucos adicionando elementos nele, até encontrar um que já esteja:

def verificar_lista(lista):
    s = set()
    return any(x in s or s.add(x) for x in lista)

A ideia é verificar se o elemento já está no set, e caso não esteja, adiciona. Se encontrar um elemento que já esteja, any retorna True, indicando que o elemento é repetido.


Agora vamos comparar o desempenho destas soluções com as outras respostas. Fazendo um teste rápido com o módulo timeit:

from collections import Counter

def set1(lista): # solução de outra resposta, com set
    return len(set(lista)) != len(lista)

def set2(lista): # set com any
    s = set()
    return any(x in s or s.add(x) for x in lista)

def counter(lista): # collections.Counter
    return len(Counter(lista)) != len(lista)

def sublista(lista): # solução de outra resposta, com sub-listas
    for posicao, numero in enumerate(lista):
        if numero in lista[posicao+1:]:
            return True
    else:
        return False

from timeit import timeit

listas = [ [1, 9, 2, 4, 3, 3, 2], [1, 2, 3, 4, 5, 6, 7] ]
funcoes = ['set1', 'set2', 'counter', 'sublista']
# executa 1 milhão de vezes cada teste
for func in funcoes:
    print(f'{func:>8}', timeit(f'for lista in listas:\n\t{func}(lista)', number=1000000, globals=globals()))

Os tempos podem variar de uma máquina para outra, mas enfim, na minha o resultado foi (tempos em segundos):

    set1 1.2527604
    set2 3.2695244
 counter 5.8885616
sublista 2.962209399999999

Ou seja, a solução com set da outra resposta foi mais rápida, seguida da solução com sub-listas. Depois, set com any foi a terceira e Counter foi a pior. No IdeOne.com e no Repl.it os tempos foram diferentes, mas o resultado foi similar (obs: no IdeOne.com tive que diminuir a quantidade de vezes porque estava estourando o tempo limite).


Claro que para poucas listas pequenas a diferença será insignificante. E o resultado também depende das listas. Por exemplo, fiz outro teste com esta lista:

[1, 1] + list(range(1000))

Ou seja, dois elementos repetidos logo no início e mais mil números (de 0 a 999). O resultado foi:

    set1 18.3008393
    set2 0.9740259000000009
 counter 45.1233362
sublista 2.3400793999999934

Neste caso, a solução alternativa com set (a que usa any) foi mais rápida, porque ela detecta logo nas primeiras iterações que o elemento está repetido (o any interrompe o loop logo que encontra um repetido, então ele só itera pelos 2 primeiros números).

A segunda solução mais rápida foi a com sub-listas, também porque ela encerra o for logo que encontra o número repetido (a demora em relação à primeira solução talvez se dê por ter que construir a sub-lista com 999 elementos).

Já a solução com set da outra resposta demorou mais porque precisa construir todo o set primeiro, para só então pegar o tamanho.

E a solução com Counter foi a pior de todas (muito pior, aliás), pois ela precisou contabilizar a quantidade de todos os 1000 elementos (e isso confirma que usar Counter neste caso é realmente um exagero).

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