Usuwanie duplikatów w C# z HashSet

Czego szuka rekruter: znajomość HashSet<T>, złożoność O(n) vs O(n²), zachowanie kolejności
Poziom: Junior / Mid

Zadanie

Napisz funkcję, która usuwa duplikaty z tablicy lub listy i zwraca tylko unikalne elementy. Zachowaj kolejność pierwszego wystąpienia.

Czego szuka rekruter

To zadanie o wyborze właściwej struktury danych. HashSet<T> daje O(1) przy sprawdzaniu czy element już istnieje — pełne omówienie tej kolekcji, w tym dlaczego wymaga poprawnego GetHashCode/Equals dla własnych typów, znajdziesz w artykule HashSet w C#. Zagnieżdżona pętla daje O(n²). Rekruter patrzy:

• Czy kandydat zna HashSet<T> i wie dlaczego jest właściwy tutaj
• Czy zachowuje kolejność — HashSet nie gwarantuje porządku
• Czy zna LINQ Distinct() i rozumie kiedy go używać

Najczęstszy błąd: zagnieżdżona pętla O(n²) z Contains na liście. List<T>.Contains to O(n), więc cała operacja to O(n²).

❌ Naiwne rozwiązanie — O(n²)

static int[] RemoveDuplicatesNaive(int[] arr)
{
    var result = new List<int>();
    foreach (var item in arr)
    {
        if (!result.Contains(item))  // List.Contains = O(n) → całość O(n²)
            result.Add(item);
    }
    return result.ToArray();
}

✅ Optymalne rozwiązanie — O(n) z HashSet

static T[] RemoveDuplicates<T>(T[] arr)
{
    if (arr == null) throw new ArgumentNullException(nameof(arr));

    var seen = new HashSet<T>();
    var result = new List<T>(arr.Length);

    foreach (var item in arr)
    {
        if (seen.Add(item))  // HashSet.Add zwraca false jeśli element już istnieje
            result.Add(item);
    }

    return result.ToArray();
}

HashSet.Add robi dwie rzeczy naraz: sprawdza czy element istnieje (O(1) amortyzowane) i dodaje go jeśli nie istnieje. Zwraca true przy nowym elemencie, false przy duplikacie.

LINQ — Distinct()

static T[] RemoveDuplicatesLinq<T>(T[] arr)
    => arr?.Distinct().ToArray() ?? throw new ArgumentNullException(nameof(arr));

Distinct() wewnętrznie używa HashSet<T> — ta sama złożoność O(n), o wiele mniej kodu. W produkcji to poprawne podejście.

Gdy chcesz usunąć duplikaty obiektów po właściwości

record Product(int Id, string Name);

var products = new[]
{
    new Product(1, "Klawiatura"),
    new Product(2, "Mysz"),
    new Product(1, "Klawiatura"),  // duplikat
};

// Deduplikacja po Id:
var unique = products
    .GroupBy(p => p.Id)
    .Select(g => g.First())
    .ToArray();

// Lub z DistinctBy (NET 6+):
var unique2 = products.DistinctBy(p => p.Id).ToArray();

Deduplikacja bez modyfikowania typu — IEqualityComparer<T>

Nadpisanie GetHashCode/Equals na klasie (patrz artykuł o HashSet) działa tylko wtedy, gdy masz dostęp do jej definicji i chcesz, żeby zawsze porównywała się w ten sam sposób. Czasem potrzebujesz innej reguły porównania tylko w jednym konkretnym miejscu — np. deduplikacji stringów bez rozróżniania wielkości liter, bez zmieniania globalnego zachowania typu string. Do tego służy IEqualityComparer<T> przekazywany jako parametr:

var slowa = new[] { "Ala", "ala", "Basia", "BASIA", "Kot" };

// Distinct z domyślnym porównaniem — "Ala" i "ala" to dwa różne elementy
var domyslne = slowa.Distinct().ToArray();
// ["Ala", "ala", "Basia", "BASIA", "Kot"] — 5 elementów

// Distinct z komparatorem ignorującym wielkość liter
var ignorujacWielkosc = slowa.Distinct(StringComparer.OrdinalIgnoreCase).ToArray();
// ["Ala", "Basia", "Kot"] — 3 elementy, zachowana wielkość liter pierwszego wystąpienia

StringComparer.OrdinalIgnoreCase to gotowa implementacja IEqualityComparer<string> z biblioteki standardowej — dla własnych typów możesz napisać analogiczny komparator, implementując interfejs samodzielnie, bez ruszania definicji klasy, którą deduplikujesz.

Testy jednostkowe

[Fact]
public void RemoveDuplicates_TypicalArray_PreservesOrder()
{
    var result = RemoveDuplicates(new[] { 3, 1, 2, 1, 3, 4 });
    Assert.Equal(new[] { 3, 1, 2, 4 }, result);
}

[Fact]
public void RemoveDuplicates_NoDuplicates_ReturnsSameElements()
{
    var result = RemoveDuplicates(new[] { 1, 2, 3 });
    Assert.Equal(new[] { 1, 2, 3 }, result);
}

[Fact]
public void RemoveDuplicates_AllSame_ReturnsSingleElement()
{
    var result = RemoveDuplicates(new[] { 5, 5, 5, 5 });
    Assert.Equal(new[] { 5 }, result);
}

[Fact]
public void RemoveDuplicates_Empty_ReturnsEmpty()
{
    var result = RemoveDuplicates(Array.Empty<int>());
    Assert.Empty(result);
}

Co powiedzieć na rozmowie

“List.Contains to O(n), więc zagnieżdżona pętla to O(n²). HashSet ma O(1) amortyzowane dla Add i Contains, więc całe usuwanie duplikatów to O(n). W produkcji użyłbym LINQ Distinct() lub DistinctBy() bo są czytelne i wewnętrznie robią to samo. HashSet bezpośrednio piszę gdy potrzebuję pełnej kontroli, custom komparatora przez IEqualityComparer<T>, lub obsługi specjalnego przypadku.”

Podsumowanie

Powiązane: zobacz pokrewne zadania na kolekcjach: Zliczanie liter i Min i max w tablicy.