HashSet pra quem sabe o que é uma List no C#
Tanto o
HashSet quanto o List são estruturas de dados em C# que permitem armazenar uma coleção de elementos. No entanto, há diferenças importantes entre eles.O
List é uma lista ordenada de elementos, onde cada elemento é acessado por um índice numérico. O List permite elementos duplicados e mantém a ordem dos elementos adicionados.Por outro lado, o
HashSet é uma coleção de elementos não ordenados e não permite elementos duplicados. O HashSet usa um algoritmo de hashing para armazenar e recuperar elementos, o que torna a verificação da presença de um elemento muito rápida em comparação com o List.Pense na situação em que você precisa encontrar o primeiro número duplicado em um array, onde o índice da segunda ocorrência desse número seja o menor possível. Nesse caso, o uso do
HashSet pode ser especialmente útil.Considere o seguinte exercício: dado um array
a que contém apenas números no intervalo de 1 a a.length, devemos encontrar o primeiro número duplicado para o qual a segunda ocorrência tem o índice mínimo. Em outras palavras, se houver mais de um número duplicado, devemos retornar o número cuja segunda ocorrência tem um índice menor do que a segunda ocorrência dos outros números duplicados. Caso não haja elementos que satisfaçam essa condição, o valor retornado será -1.Imagine que temos o seguinte array:
int[] a = {2, 3, 1, 5, 2, 4, 3};
Nesse caso, o número 2 é o primeiro número duplicado, pois aparece nas posições 0 e 4 do array. A segunda ocorrência do número 2 ocorre na posição 4, que é menor do que a segunda ocorrência dos outros números duplicados (o número 3 aparece nas posições 1 e 6, e o número 5 aparece apenas na posição 3).
Para resolver esse problema, podemos utilizar um
HashSet para armazenar os números que encontramos durante a iteração pelo array. Ao percorrer o array, podemos verificar se cada número já existe no HashSet. Se já existir, encontramos o primeiro número duplicado e podemos retorná-lo. Caso contrário, adicionamos o número ao HashSet e continuamos a iteração.Por isso, no exemplo apresentado, usamos um
HashSet para implementar a solução.int FindFirstDuplicate(int[] array) { HashSet<int> numbers = new HashSet<int>(); foreach (int num in array) { if (numbers.Contains(num)) { return num; } numbers.Add(num); } return -1; }
Nesse exemplo, criamos um
HashSet chamado numbers para armazenar os números encontrados. Em seguida, percorremos o array utilizando um loop foreach e verificamos se cada número já existe no HashSet. Se já existir, retornamos o número duplicado. Caso contrário, adicionamos o número ao HashSet e continuamos a iteração.Usar um
List exigiria percorrer todo o List para verificar se cada elemento já foi adicionado anteriormente, o que levaria O(n²) tempo no pior caso.Por outro lado, usar um
HashSet permite verificar rapidamente se um elemento já foi adicionado anteriormente, em O(1) tempo no melhor caso. Como o HashSet não permite elementos duplicados, o primeiro elemento duplicado que encontrarmos será a duplicata que procuramos.