Нахождение дубликатов в массиве JavaScript: эффективные методы
Быстрый ответ
Чтобы определить дублирующиеся значения в массиве, можно сочетать метод filter
с методом indexOf
, чтобы отслеживать первое вхождение каждого элемента:
const duplicates = [1, 2, 2, 3, 1].filter((e, i, a) => a.indexOf(e) !== i);
// duplicates => [2, 1]
Здесь метод filter
обходит массив (a
), сравнивая индекс текущего элемента (i
) с индексом его первого вхождения (indexOf(e)
). Если они не совпадают, элемент считается дубликатом.
Детальный анализ и оптимальные решения
Указанный выше подход подходит для небольших массивов, но его эффективность уменьшается с ростом размера массива из-за сложности алгоритма O(N^2). В таких случаях предпочтительнее использовать более производительные методы.
Оптимизация через сортировку
Сортировка может облегчить поиск повторений, располагая дублирующиеся элементы подряд:
function findDuplicates(data) {
let sorted = data.slice().sort((a, b) => a – b);
let results = [];
for (let i = 1; i < sorted.length; i++) {
if (sorted[i – 1] === sorted[i]) {
results.push(sorted[i]);
}
}
return [...new Set(results)];
}
Применение Set
и filter
для компактного решения
Комбинация Set
и filter()
можно использовать в качестве компактного решения:
const findUniqueDuplicates = arr => arr.filter((e, i, a) => a.indexOf(e) !== i && a.lastIndexOf(e) === i);
Эта функция находит уникальные дубликаты, то есть значения, повторяющиеся более одного раза, но без повторений в итоговом массиве.
Работа с большими наборами данных
При работе с большими объемами данных учитывайте временную и пространственную сложность алгоритма.
Выбор алгоритма
Правильным выбором являются алгоритмы, осуществляющие минимальное число избыточных операций. Для больших массивов рекомендуется использовать методы, основанные на sort
и Set
.
Работа с различными типами данных
JavaScript позволяет хранить разные типы данных в одном массиве, что может создать потребность в специализированной функции сортировки для объектов и массивов.
Совместимость с браузерами
Удостоверьтесь, что ваш код будет работать правильно в целевых браузерах. При необходимости примените полифиллы или более совместимые методы.
Визуализация
Предположим, у нас есть аквариум с рыбами:
🐠🐟🐡🐠🐡🐠
Пять обитателей, среди которых есть дублирующиеся.
Сканер рыб: 🧐🔍
Дубликаты: [🐠, 🐡]
Распознаем дубликаты.
function getDuplicates(array) {
}
Функция "ловит" повторяющихся рыбок:
🎣 Улов: [🐠, 🐠, 🐡, 🐠, 🐡]
Уникальные: [🐟]
Уникальные особи остаются вне "сети".
Уникальность один раз, дублирование множество раз: работа с уникальными дубликатами
Для того, чтобы каждый дубликат отображался в массиве только один раз, применяются дополнительные методы.
Использование Set
Set
позволяет хранить уникальные значения, идеально подходя для создания списка без повторений:
const uniqueDuplicates = Array.from(new Set(duplicates));
Сочетание reduce
и indexOf
С помощью этой связки можно "собрать" дубликаты, без повторного их включения:
const uniqDupsReducer = (acc, e, i, array) => {
if (array.indexOf(e) !== i && acc.indexOf(e) === -1) acc.push(e);
return acc;
};
const uniqueDups = [1, 2, 2, 3, 1].reduce(uniqDupsReducer, []);
Полезные материалы
- Функция Array.prototype.filter() на MDN — документация о фильтрации массивов.
- Функция Array.prototype.map() на MDN — информация по преобразованию массивов.
- Функция Array.prototype.reduce() на MDN — данные о способах комбинирования элементов массива.
- Обсуждение методов поиска дубликатов на Stack Overflow — советы и лайфхаки с форума разработчиков.
- Объект Set на MDN — подробности о работе с уникальными значениями.