Множество: мешок, который не терпит повторов

Tier 1Бесплатно

Elman HuseynovОбновлено 2026-10-21

Уровень

Где применяется

1. Задача

В уроке про Big-O ты научился замечать ловушку O(n²): цикл внутри цикла по одному и тому же списку. Чаще всего она прячется в вопросе «есть ли в списке повтор?». Если сравнить каждый элемент со всеми остальными, то список из миллиона элементов потребует миллион на миллион сравнений.

Есть структура данных, которая отвечает на вопрос «я уже видел это значение?» примерно за один шаг, какой бы длинный ни был список. Она называется множество (Set). С ней вместо цикла в цикле, O(n²), хватает одного прохода по списку. С этого урока начинается небольшая группа таких встроенных структур.

2. Простыми словами

Множество (Set) это мешок значений с одним правилом: одно и то же значение он дважды не хранит. Возьми список ["a", "b", "a", "c"] и клади его значения в пустой мешок по одному. "a" ложится в мешок. "b" тоже. Второе "a" ничего не меняет: "a" уже внутри. "c" ложится в мешок. Теперь в нём "a", "b" и "c", каждое по одному разу.

Ещё мешку можно задать вопрос: «есть ли внутри "b"?» Ответ, да или нет, приходит сразу. Вытряхивать мешок и перебирать его содержимое не нужно.

Итак, мешок хранит каждое значение в одном экземпляре и сразу говорит, есть ли в нём нужное значение.

3. Идея

В JavaScript такой мешок уже встроен. Он называется Set (множество): коллекция, которая хранит каждое значение не больше одного раза.

С ним ты делаешь три вещи:

bag.add(x): положить x. Если x уже в мешке, ничего не меняется.
bag.has(x): спросить, есть ли x в мешке. Ответ true или false приходит примерно за один шаг.
bag.delete(x): вынуть x.

А bag.size говорит, сколько разных значений в мешке сейчас.

Ради «примерно одного шага» множество и берут. Обычный массив тоже умеет сказать, есть ли в нём значение, но для этого он проходит весь массив: indexOf и includes стоят O(n). Множество устроено так, что время has не зависит от того, сколько в нём значений. Как это устроено, ты увидишь через несколько уроков, в теме про хеширование. Пока прими на веру, что has, add и delete занимают примерно по одному шагу.

Чтобы получить все разные значения в порядке первой встречи, пройди список один раз. Для каждого значения проверь множество. Если значения там нет, добавь его во множество и оставь в ответе. Если оно там уже есть, пропусти его. Пример на ["a", "b", "a", "c"]: a новое, оставляем; b новое, оставляем; a уже во множестве, пропускаем; c новое, оставляем. Результат: ["a", "b", "c"].

Чтобы просто узнать, есть ли хоть один повтор, тоже иди по списку. Как только has ответит «да», останавливайся и возвращай true. На ["a", "b", "a"] это случится на третьем элементе. Если дошёл до конца и ни разу не услышал «да», повторов нет.

4. Во что это обходится

Каждый has, add и delete стоит примерно O(1), то есть один шаг, сколько бы значений ни было во множестве. Прочитать size тоже стоит O(1).

Убрать повторы из списка в n значений стоит O(n) по времени. Это один проход, и на каждое значение приходится один has и, возможно, один add. По памяти это O(n) в худшем случае, когда все значения разные и все попадают во множество. Эта лишняя память и есть цена: вместо вложенного цикла за O(n²) остаётся один проход.

Проверка на повтор тоже стоит O(n) по времени и O(n) по памяти в худшем случае. Но она может закончиться раньше: как только встречается уже виденное значение, функция возвращает ответ и остаток списка не читает.

5. Где это встречается

Из потока ID посетителей или тегов убирают повторы, а потом считают «уникальных посетителей» или «разные теги». Защищаются от повторной обработки: держат множество ID уже обработанных запросов и отбрасывают ID, который уже встречался. Краулер (программа, которая обходит сайты и скачивает страницы) запоминает уже скачанные страницы, чтобы не ходить по кругу вечно. Форма не даёт ввести повтор, например дважды одного получателя письма. Когда вопрос звучит просто как «это уже есть в коллекции?», первым выбором будет множество. Ответ остаётся дешёвым, как бы ни росла коллекция.

На LeetCode

Задачи, где нужно понять, встречалось ли значение раньше, есть ли в списке повтор или какие значения есть в обоих списках. Множество (Set) отвечает на каждый такой вопрос примерно за один шаг.

217.Contains Duplicate (откроется в новой вкладке)Лёгкая
Это hasDuplicate из урока, и true возвращается, как только has ответит «да».
349.Intersection of Two Arrays (откроется в новой вкладке)Лёгкая
Положи первый массив в множество, затем собери значения второго, которые в нём есть, каждое по одному разу.
771.Jewels and Stones (откроется в новой вкладке)Лёгкая
Сложи буквы драгоценностей в множество и посчитай камни, которые в нём есть.
128.Longest Consecutive Sequence (откроется в новой вкладке)Средняя
Когда все числа лежат в множестве, начинай счёт с x, только если в нём нет числа x минус 1.

Твоя задача (Tier 1)

Напиши две функции: dedupe(items) и hasDuplicate(items).

Обе используют множество: мешок, где каждое значение лежит только один раз. Используй его как память «я это уже видел?».

Вход: items, список значений (текст или числа). Пример: ["a", "b", "a"].
dedupe возвращает новый список, где каждое значение оставлено один раз, в порядке первой встречи.
hasDuplicate возвращает true, если какое-нибудь значение встречается больше одного раза, иначе false.

Шаги:

Заведи пустое множество seen.
Для dedupe: иди по списку. Если значения нет в seen, добавь его в seen и в список-ответ. В конце верни список-ответ.
Для hasDuplicate: иди по списку. Если значение уже есть в seen, верни true. Иначе добавь его в seen. Если дошёл до конца, верни false.

Готово, когда проходят все тесты:

dedupe:

["a","b","a","c","b"] -> ["a","b","c"]
["a","b","c"] -> ["a","b","c"] (все разные, ничего не убрано)
["z","z","z"] -> ["z"] (все одинаковые, оставлен один)
["x", 7, "x", 7, "y"] -> ["x", 7, "y"] (список с текстом и числами)
[] -> [] (пустой список, не должно падать)

hasDuplicate:

["a","b","a"] -> true ("a" повторяется)
[1, 2, 3] -> false (все разные)
["z","z","z"] -> true
["x", 7, "y"] -> false
[] -> false (пустой список)

Практика

dedupe / hasDuplicate

export function dedupe(items) {
  // Your code here. The task is described in the box above the editor.
}

export function hasDuplicate(items) {
  // Your code here. The task is described in the box above the editor.
}

Ты здесь как гость

Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.

Завести бесплатный аккаунт Войти

Лестница подсказок

Застрял? Открывай по одной, но сначала попробуй сам.

НазадПерестроить массив, не заводя второй ДалееMap: помеченное хранилище ключ → значение