Удалить дубликаты из массива, сохранив порядок первого появления, за O(n)
Реализуйте RemoveDuplicates(nums), возвращающую новый массив без дубликатов, СОХРАНЯЯ порядок первого появления. Требования: O(n) по времени с использованием HashSet<int> — один проход. [3, 1, 3, 2, 1] должен вернуть [3, 1, 2] (первые вхождения, исходный порядок). Не сортируйте — это разрушит порядок.
public static int[] RemoveDuplicates(int[] nums)
{
// ваш код здесь
return null;
}Допишите реализацию.
Пройдите nums один раз с HashSet<int> seen и List<int> result. Для каждого значения seen.Add(n) возвращает false, если оно уже есть — пропускаем; при true добавляем в result. Верните result.ToArray(). Множество даёт O(1) проверку, поэтому весь проход — O(n), а порядок сохраняется.
- ✗Сортировать сначала, разрушая требуемый порядок первого появления
- ✗Проверять вхождение вложенным циклом, делая это O(n²) вместо O(n)
- ✗Возвращать
set.ToArray()напрямую, что не гарантирует порядок вставки
- →Почему возврат bool из
HashSet.Addэкономит отдельный вызовContains? - →Как дедуплицировать поток, который не помещается в память?
Задача
Вернуть элементы массива без дубликатов, сохранив порядок первого появления.
public static int[] RemoveDuplicates(int[] nums)
{
var seen = new HashSet<int>();
var result = new List<int>();
foreach (int n in nums)
if (seen.Add(n)) // true только при первом появлении n
result.Add(n);
return result.ToArray();
}Как это работает
Мы идём по массиву один раз. HashSet<int> запоминает уже встреченные значения и даёт проверку вхождения за O(1).
Ключевая деталь — seen.Add(n) возвращает bool: true, если n добавлено впервые, и false, если оно уже было. Это позволяет объединить проверку и вставку в одно действие — нет нужды в отдельном Contains. При первом появлении значение дописывается в result, при повторном — пропускается.
Поскольку элементы добавляются в result строго в порядке их первого появления, исходный порядок сохраняется. Один проход с O(1)-операциями на шаг даёт O(n) по времени. Сортировка сломала бы порядок, а вложенная проверка превратила бы это в O(n²).
