LogoData Structures & Algorithms

Хеш-таблица: удаление дубликатов (Deduplicate)

Использует хеш-таблицу (в JS – Set) для отметки «уже встречено». Идём слева направо: если элемента ещё нет в множестве – добавляем в результат и помечаем как «seen»; если был – пропускаем. В итоге получаем массив без дубликатов, сохраняя порядок первого появления. Эквивалент короткой записи [...new Set(arr)].
Сложность:

Время – O(n) в среднем, Память – O(n)

deduplicate.ts
1

2// Удаление дубликатов с сохранением порядка первого появления
3function dedupIterative<T>(arr: T[]): T[] {
4    const seen = new Set<T>();
5    const res: T[] = [];
6    for (const x of arr) {
7        if (!seen.has(x)) {
8            seen.add(x);
9            res.push(x);
10        }
11}
12return res;
13}
14

15// Короткая версия через Set
16function dedupWithSet<T>(arr: T[]): T[] {
17    return [...new Set(arr)];
18}
19

20dedupIterative(["a","b","a","c","b"]) // -> ["a","b","c"]
21dedupWithSet(["a","b","a","c","b"]) // -> ["a","b","c"]
22

23dedupIterative([3,1,3,2,2,1]) // -> [3,1,2]
24dedupWithSet([3,1,3,2,2,1]) // -> [3,1,2]
25

26dedupIterative([]) // -> []
27dedupWithSet([]) // -> []
28

29dedupIterative([1,1,1,1]) // -> [1]
30dedupWithSet([1,1,1,1]) // -> [1]
31