Como Encontrar Duplicados em uma Lista?

Raciocínio lógico é uma habilidade fundamental para qualquer programador. Para continuar aprimorando a minha, utilizo frequentemente plataformas como HackerRank e LeetCode. Elas oferecem desafios de programação para todos os níveis, permitindo melhorar a capacidade de resolução de problemas enquanto praticamos estruturas de dados como ferramentas para soluções eficazes.

Problema

Durante um dos exercícios, encontrei um problema interessante que vale a pena compartilhar. À primeira vista, ele parece bastante simples:

Dado um vetor de inteiros nums contendo n + 1 inteiros, onde cada inteiro está no intervalo [1, n], retorne o número duplicado.

• Exatamente um inteiro aparece mais de uma vez.
• Você não pode modificar o vetor (nums) e deve usar apenas espaço extra constante.

Restrições

• 1 ≤ n ≤ 10⁵
• nums.length == n + 1
• 1 ≤ nums[i] ≤ n
• Todos os inteiros em nums aparecem exatamente uma vez, exceto um que aparece duas ou mais vezes.

A garantia de que existe um número duplicado vem do Princípio da Casa dos Pombos — um conceito fundamental da matemática. Vale a pena conferir sua prova, pois ela se relaciona elegantemente com vários cenários do mundo real.

O que torna esse problema realmente desafiador é a restrição adicional:

Você deve resolver o problema sem modificar o vetor de entrada e utilizando apenas espaço extra constante.

Essa restrição impede o uso de mapas de hash ou conjuntos, tornando abordagens tradicionais inviáveis.

Solução Ingênua (Ignorando Restrições)

Este é um problema clássico com uma solução bem conhecida que ignora as restrições inicialmente, o que ajuda a construir entendimento.

Vamos começar com uma abordagem direta:
Se ordenarmos o vetor, quaisquer elementos duplicados ficarão adjacentes.

Etapas:

1. Ordenar o vetor nums.
2. Iterar sobre o vetor.
3. Se algum elemento for igual ao anterior, retorná-lo.

Código em Python

def findDuplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return nums[i]

Complexidade de Tempo e Espaço

• Complexidade de Tempo: O(n log n)
  • A ordenação leva O(n log n) e a iteração O(n).
• Complexidade de Espaço:
  • O(log n) ou O(n) dependendo da implementação do sort:
    • Timsort do Python: Pior caso O(n)
    • Arrays.sort() do Java: O(log n)
    • sort da STL em C++: O(log n)

Embora eficaz, essa solução viola as restrições por modificar o vetor e utilizar mais do que espaço constante.

Solução Ideal: Detecção de Ciclo

Uma abordagem mais sofisticada é modelar o vetor como uma lista encadeada, onde cada índice aponta para o valor nesse índice. Devido ao valor duplicado, um ciclo deve existir. O problema se reduz à detecção de ciclo em listas encadeadas — especificamente, encontrar o início do ciclo.

Esse conceito é ilustrado abaixo:

Trata-se essencialmente do problema Linked List Cycle II.

Vamos ampliar o vetor para melhor visualização:

Algoritmo da Tartaruga e da Lebre de Floyd

Este algoritmo usa dois ponteiros que se movem em velocidades diferentes:

Fase 1: Encontrando a Interseção

• hare = nums[nums[hare]] (movimenta-se duas vezes mais rápido)
• tortoise = nums[tortoise] (movimenta-se uma vez)
• Eles se encontram dentro do ciclo.

Observação: o ponto de interseção nem sempre é o início do ciclo.

Fase 2: Encontrando a Entrada do Ciclo

Reinicie o ponteiro tortoise para o início (nums[0]) e mova ambos com a mesma velocidade. Eles se encontrarão na entrada do ciclo, que é o número duplicado.

Código em Python

def findDuplicate(nums):
    # Fase 1: Encontrar o ponto de interseção
    tortoise = hare = nums[0]
    while True:
        tortoise = nums[tortoise]
        hare = nums[nums[hare]]
        if tortoise == hare:
            break

    # Fase 2: Encontrar a entrada do ciclo
    tortoise = nums[0]
    while tortoise != hare:
        tortoise = nums[tortoise]
        hare = nums[hare]

    return hare

Complexidade de Tempo e Espaço

• Complexidade de Tempo: O(n)
• Complexidade de Espaço: O(1)

Esta solução é elegante e ótima, transformando um problema aparentemente de array em uma detecção de ciclo com ponteiros.

Dica: Se estiver com dificuldades para visualizar o processo, imprima no console os valores dos ponteiros tortoise e hare para acompanhar seus caminhos.

Referências

• 📺 Explicação em vídeo
• 📘 Wikipedia - Detecção de Ciclo
• 💻 Problema no LeetCode