Нахождение дубликатов в массиве 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, []);

Полезные материалы

1. Функция Array.prototype.filter() на MDN — документация о фильтрации массивов.
2. Функция Array.prototype.map() на MDN — информация по преобразованию массивов.
3. Функция Array.prototype.reduce() на MDN — данные о способах комбинирования элементов массива.
4. Обсуждение методов поиска дубликатов на Stack Overflow — советы и лайфхаки с форума разработчиков.
5. Объект Set на MDN — подробности о работе с уникальными значениями.