Задача на удаление дубликатов, на размышление даётся 30 секунд

    Не так давно проходил собеседование в одну компанию, где одной из задач было удаление дубликатов элементов отсортированного списка. Наверняка вы сейчас скажете "Да это ж легкотня" или "Да я такое 100 раз делал!". И будете правы. Но нюансы есть всегда.

    Именно так нейросеть "Kandinsky 3.1" поняла мой запрос про генерацию элементов массива, состоящего из натуральных чисел. :D Тут предстоит ещё большая работа в обучении.

    Но вернемся к задаче. Итак, нам дан такой метод:

private static void RemoveDuplicates(ref List<int> items)
{
   // ...
}

  ❌Способ 1. Давайте заюзаем SortedSet, положим туда все элементы списка и его вернем из метода? Звучит логично, но тут я наталкиваюсь на 1-е ограничение по задаче: сигнатуру метода менять нельзя. В таком случае надо заново выделять память под другой список (с уже удаленными после SortedSet-a элементами).

private static void RemoveDuplicates(ref List<int> items)
{
    var temp = new SortedSet<int>();
    foreach (var item in items)
    {
        temp.Add(item);
    }
    
    items = temp.ToList();       
}

  И тут получаю 2-е ограничение: элементов может быть миллион. А теперь представим, сколько аллокаций памяти в куче будет при таком весьма бешенном размещении элементов коллекций. Т.к. там будет располагаться исходный массив, множество элементов SortedSet, а также результирующий список. Звучит не очень, ищем способ получше.

  ❌Способ 2. В цикле за O(n) проходимся по исходному списку и просто удаляем элемент, если он равен предыдущему. Вроде бы просто как дважды два, реализуем:

private static void RemoveDuplicates(ref List<int> items)
{
    for (int i = 1; i < items.Count; i++)
    {
        if (items[i] == items[i-1])
        {
            items.RemoveAt(i);
            i--;
        }
    }        
}

    Как вы уже догадались, и такой вариант решения задачи таит в себе очевидный изъян - операция удаления из списка не самая оптимальная из-за частого перераспределения памяти.

    ❌Способ 3. А что если нам просто завести булевый массив, в котором мы будем просто хранить логические флажки (берём или не берём элемент массива в результирующую коллекцию). Пример кода я не буду приводить, тут и так понятно, что мы выделяем память под, грубо говоря, миллион bool-элементов, а затем повторно выделяем память под итоговый список.

    ✅Способ 4. А теперь разберем корректный солюшн. Обойдёмся без вспомогательных коллекций и удаления элементов списка в цикле. Для этого нам нужно запастись терпением двумя вспомогательными индексами. 1-й из них будет предназначен для чтения, 2-й - для записи. И с самого начала у нас writeIndex будет "отставать" на 1 позицию от readIndex. И теперь, проходя по циклу и встречая первый каждый новый уникальный элемент, мы будем записывать его на новое место, предварительно увеличив writeIndex. Ну и конечно надо не забыть удалить лишние элементы из массива.
    

     Итак, засучив рукава, пора реализовывать данную концепцию. Должно получиться следующее:

private static void RemoveDuplicates(ref List<int> items)
{
    var writeIndex = 0;
    for (int readIndex = 1; readIndex < items.Count; readIndex++)
    {
        if (items[writeIndex] != items[readIndex])
        {
            items[++writeIndex] = items[readIndex];
        }
    }

    items.RemoveRange(writeIndex + 1, items.Count - writeIndex - 1);
}

    Чем же хорош данный способ? Он работает строго за O(n) операций, нет дополнительных выделений памяти и операция удаления у нас только одна.

    Надеюсь, что данная статья стала новой пищей для размышлений у вас, уважаемого читателя, и что данные размышления и способы решения задач пригодятся в ваших проектах!