Не так давно проходил собеседование в одну компанию, где одной из задач было удаление дубликатов элементов отсортированного списка. Наверняка вы сейчас скажете "Да это ж легкотня" или "Да я такое 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) операций, нет дополнительных выделений памяти и операция удаления у нас только одна.
Надеюсь, что данная статья стала новой пищей для размышлений у вас, уважаемого читателя, и что данные размышления и способы решения задач пригодятся в ваших проектах!
С появлением ключевого слова var появилась возможность уменьшить количество шаблонного кода и писать более компактные выражения. Напомню, что это произошло достаточно давно, аж в 2007 году и ещё в C# версии 3.0.
