Уникализация значений в массиве
Необходимо написать функцию, принимающая аргументом массив целых чисел и возвращающая новый массив, состоящий только из уникальных значений исходного массива. Порядок элементов должен остаться исходным.
unique([1, 1, 2, 2, 4, 2, 3, 7, 3]); // => [1, 2, 4, 3, 7]
Примеры:
unique([1, 1, 2, 2, 4, 2, 3, 7, 3]); // => [1, 2, 4, 3, 7]
unique([1, 1, 1, 1, 2, 2, 4, 2, 3, 3]); // => [1, 2, 4, 3]
unique([1, 1, 2, 2, 4, 2, 3, 7, 3, 8, 9, 8]); // => [1, 2, 4, 3, 7, 8, 9]
Теория и разбор
Set — это коллекция значений, в которой каждое значение может встречаться только один раз, то есть значения уникальны.
При переборе Set элементы посещаются в порядке добавления, поэтому при создании new Set(arr) сохраняется порядок первых появлений значений из массива.
Почему порядок сохраняется
Идея задачи: «в результирующий массив должно попасть только первое появление каждого числа».
Если идти слева направо и добавлять число только тогда, когда оно встречено впервые, то порядок «первых появлений» автоматически совпадает с порядком исходного массива.
Это можно представить так (состояние после каждого шага):
arr: [1, 1, 2, 2, 4, 2, 3, 7, 3]
seen: {} -> {1} -> {1} -> {1,2} -> {1,2} -> {1,2,4} -> {1,2,4} -> {1,2,4,3} -> {1,2,4,3,7} -> {1,2,4,3,7}
result: [] -> [1] -> [1] -> [1,2] -> [1,2] -> [1,2,4] -> [1,2,4] -> [1,2,4,3] -> [1,2,4,3,7] -> [1,2,4,3,7]
Как определяется «одинаковость» в Set
В JavaScript при добавлении в Set значения сравниваются по правилам, близким к строгому равенству для чисел (то есть 1 и 1 считаются одинаковыми).
Также важно знать частный случай: NaN в Set считается тем же самым значением при повторном добавлении, поэтому дубликаты NaN будут удалены (хотя обычное сравнение NaN !== NaN возвращает true).
Сложность по времени и памяти
Ниже — практичное сравнение подходов:
| Подход | Идея | Время (типично) | Память | Когда выбирать |
|---|---|---|---|---|
Set (через цикл) | Проверять seen.has, затем add | Обычно близко к O(n) | O(n) | На практике почти всегда |
Set (через new Set + spread) | Уникальность «встроенно» | Обычно близко к O(n) | O(n) | Когда важна краткость |
filter + indexOf | Оставлять только первое вхождение | Часто O(n^2) | O(1) доп. | Для небольших массивов, как учебный |
| Объект-словарь | Хранить «видели/не видели» по ключу | Обычно близко к O(n) | O(n) | Когда Set нельзя/не хочется, и значения простые |
Подводные камни
- Возврат должен быть новым массивом: изменять исходный массив не требуется, поэтому в решениях создается
resultили используется новый массив изSet. - Для «уникальности объектов» (например,
{a:1})Setсчитает уникальность по ссылке, а не по содержимому; в задаче с целыми числами это не проявляется. - Вариант с объектом-словарем требует аккуратности с ключами; безопаснее создавать словарь как
Object.create(null), чтобы не зависеть от свойств прототипа (в приведенном коде это учтено). - Если требуется уникальность «по модулю», «с округлением» или по любому другому правилу, то
Setпо умолчанию не подойдет напрямую, так как он не умеет преобразовывать ключ автоматически; потребуется явное преобразование значения перед проверкой.
Кратко: достаточно пройти по массиву слева направо и добавлять элемент в результат только при первом появлении; наиболее практично это делается через Set, так как он хранит только уникальные значения и сохраняет порядок добавления при переборе.