Contains Duplicate

Q: Qual é a complexidade de tempo de Contains Duplicate?

A solução com conjunto hash tem complexidade de tempo média O(n) e usa espaço extra O(n) . Ordenar primeiro leva O(n log n) de tempo e não requer um array extra se você puder reordenar a entrada. Comparar todos os pares leva O(n²) de tempo.

Q: Você consegue resolver Contains Duplicate sem espaço extra?

Sim, se você puder reordenar o array: ordene-o no próprio lugar e compare cada valor com seu vizinho. Isso troca o conjunto O(n) por um tempo de O(n log n) . Sem reordenar e sem memória extra, a única opção restante é a verificação de pares O(n²) .

Q: Por que um conjunto hash torna a verificação rápida?

Um conjunto hash armazena valores com base em seus hashes, então verificar se contém um valor leva tempo constante, em média, em vez de exigir uma varredura. Cada elemento custa uma busca e uma inserção, o que torna linear o percurso completo.

Q: Comparar o tamanho do conjunto com o comprimento do array é uma solução válida?

Sim. Criar um conjunto com todos os elementos de nums e verificar se ele é menor que o array fornece a resposta correta em O(n) de tempo. A versão com loop costuma ser melhor porque retorna assim que encontra a primeira repetição, enquanto criar o conjunto inteiro sempre lê todos os valores.

FácilHashing

+10

Você recebe um array de números inteiros nums. Retorne true se algum valor aparecer nele pelo menos duas vezes, e false se todos os valores forem diferentes.

Função

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: os números inteiros a verificar
Retornaboolean: true se algum valor aparecer pelo menos duas vezes; caso contrário, false

Restrições

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Exemplos

Entrada: nums = [3, 1, 4, 1, 5]
Saída: true
Explicação: O valor 1 aparece no índice 1 e novamente no índice 3, então a resposta é true.

Entrada: nums = [2, 7, 1, 8]
Saída: false
Explicação: 2, 7, 1 e 8 são quatro valores diferentes, então nada se repete.

Entrada: nums = [-4, 4, 0]
Saída: false
Explicação: -4 e 4 têm o mesmo valor absoluto, mas são números diferentes, e 0 aparece uma vez, então a resposta é false.

+17 testes ocultos ao enviar

Para ir além

Você consegue parar assim que encontrar o primeiro valor repetido, em vez de sempre ler o array inteiro?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma repetição é um valor que você já encontrou antes, e o trabalho consiste em responder rapidamente à pergunta "já encontrei este valor?". Comparar cada par responde a essa pergunta, mas, para n = 10^4, isso significa n(n-1)/2, cerca de 5 × 10^7 comparações. A ordenação aproxima os valores iguais, e um conjunto hash responde à pergunta em O(1) em média, o que permite uma única passagem.

Ordene e, em seguida, compare os elementos vizinhos

Intuição

Em um array ordenado, valores iguais ficam lado a lado. [3, 1, 4, 1, 5] é ordenado como [1, 1, 3, 4, 5], e os dois 1s agora ficam juntos. Portanto, após ordenar, você só compara cada valor com o que vem imediatamente antes dele: n-1 comparações, em vez das n(n-1)/2 necessárias para testar todos os pares.

Se não houver dois vizinhos iguais, não haverá dois valores iguais em lugar algum: qualquer valor entre duas cópias de x na ordem classificada teria que ser ao mesmo tempo maior ou igual a x e menor ou igual a x; portanto, seria outro x.

A ordenação domina o tempo, com O(n log n). Ordenar nums no próprio lugar não exige um array extra, mas reordena a entrada de quem chamou; se isso não for permitido, ordene uma cópia, o que custa O(n) de espaço.

Algoritmo

Ordene nums em ordem crescente.
Percorra i de 1 até o último índice.
Se nums[i] for igual a nums[i-1], retorne true.
Após o loop, retorne false.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Uma passagem com um conjunto hash

Intuição

Percorra o array uma vez e mantenha em um conjunto hash todos os valores pelos quais você já passou. Antes de adicionar um valor, pergunte ao conjunto se ele já está lá. Para [3, 1, 4, 1, 5], o conjunto cresce até {3, 1, 4} e, quando o segundo 1 chega, o conjunto já o contém, então você retorna true sem ler o 5.

O conjunto sempre contém exatamente os valores anteriores à posição atual, então encontrar um valor significa que o valor atual apareceu antes, e chegar ao final sem encontrar nenhum significa que todos os valores são diferentes.

Uma consulta e uma inserção em um conjunto hash levam, em média, O(1) de tempo, então a passagem completa é O(n). O custo é a memória: se não houver repetição, o conjunto acaba contendo todos os n valores.

Algoritmo

Crie um conjunto hash vazio seen.
Para cada valor em nums, se ele estiver em seen, retorne true.
Caso contrário, adicione-o a seen.
Após o loop, retorne false.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Armadilhas e casos extremos

A lógica é simples, então os bugs estão nos limites dos loops e no que você compara.

Comparar todos os pares com o loop interno começando em j = i. Cada valor então corresponde a si mesmo, e a resposta é sempre true.
Comparar os vizinhos sem ordenar primeiro. Em [9, 1, 2, 3, 9], os dois 9s não estão lado a lado.
Começar o loop dos vizinhos no índice 0 e ler nums[-1]. Comece em 1, e um array com um único valor retorna corretamente false.
Tratar valores com o mesmo valor absoluto como iguais, por exemplo, usando um hash de abs(x). -4 e 4 são números diferentes.
Escrever um comparador de ordenação em C que retorna x - y. Aqui, a diferença permanece dentro de ±2 × 10^9, abaixo do limite de int de 2^31-1 = 2147483647, então ela cabe; com valores próximos aos limites de int, ocorre overflow e a ordenação fica incorreta. Retorne (x > y) - (x < y) em vez disso.

Perguntas frequentes4

Qual é a complexidade de tempo de Contains Duplicate?

A solução com conjunto hash tem complexidade de tempo média O(n) e usa espaço extra O(n). Ordenar primeiro leva O(n log n) de tempo e não requer um array extra se você puder reordenar a entrada. Comparar todos os pares leva O(n²) de tempo.

Você consegue resolver Contains Duplicate sem espaço extra?

Sim, se você puder reordenar o array: ordene-o no próprio lugar e compare cada valor com seu vizinho. Isso troca o conjunto O(n) por um tempo de O(n log n). Sem reordenar e sem memória extra, a única opção restante é a verificação de pares O(n²).

Por que um conjunto hash torna a verificação rápida?

Um conjunto hash armazena valores com base em seus hashes, então verificar se contém um valor leva tempo constante, em média, em vez de exigir uma varredura. Cada elemento custa uma busca e uma inserção, o que torna linear o percurso completo.

Comparar o tamanho do conjunto com o comprimento do array é uma solução válida?

Sim. Criar um conjunto com todos os elementos de nums e verificar se ele é menor que o array fornece a resposta correta em O(n) de tempo. A versão com loop costuma ser melhor porque retorna assim que encontra a primeira repetição, enquanto criar o conjunto inteiro sempre lê todos os valores.

Python

def containsDuplicate(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 4, 1, 5]

Esperado

true