Алгоритмы: Поиск дублей в массиве

Выполнение задачи будет на JavaScript в нескольких вариантах с примерной оценкой Big O Notation. Искомые дубли являются только примитивами.

Самое базовое решение, это 2 цикла

Самое простое решение «в лоб», если линейно пытаться решить. Нужно обязательно собрать где-то значения, в этом случае объект, чтобы сосчитать и потом получить их. Сложность алгоритма ~ O(n2)

function findDuplicates(arr) {
	const valueKeyCounters = {};
	for (let i = 0; i < arr.length; i++) {
		if (valueKeyCounters[arr[i]]) {
			continue;
		}

		for (let j = i; j < arr.length; j++) {
			if (valueKeyCounters[arr[j]]) {
			valueKeyCounters[arr[j]] = valueKeyCounters[arr[j]] + 1;
			} else {
			valueKeyCounters[arr[j]] = 1;
			}
		}
	}

	const resultArr = [];
	for (key in valueKeyCounters) {
		if (valueKeyCounters[key] > 1) {
			resultArr.push(key)
		}
	}

	return resultArr
;
}

const collection = [1, 2, 2, 3, 4, 5, 5];

Самый короткий вариант через filter и IndexOf:

Сложность алгоритма ~ O(n2)

const collection = [1, 2, 2, 3, 4, 5, 5];
const findDuplicates = arr => 
   arr.filter((item, index) => arr.indexOf(item) !== index)
console.log(findDuplicates(collection)); // результат: [2, 5]

Решение через коллекцию значений Set:

Сложность алгоритма ~ O(n)

function findDuplicates(arr) {
    const uniqueElements = new Set(arr);
    const filteredElements = arr.filter(item => {
        if (uniqueElements.has(item)) {
            uniqueElements.delete(item);
        } else {
            return item;
        }
    });

    return [...new Set(filteredElements)]
}

const collection = [1, 2, 2, 3, 4, 5, 5];
console.log(findDuplicates(collection)); // Результат: [2, 5]

Интересное решение через рекурсию:

Сложность алгоритма ~ O(n). У решения есть минус т.к мутируется сама коллекция.

const findDuplicates = (arr, double = [], len = 0, deletable = false) => {
   if(len < arr.length){
      if (deletable) {
         double.push(arr[len]);
         arr.splice(len, 1);
         len--;
      }
      return findDuplicates(arr, double, len+1, arr[len] === arr[len+1])
   };
   return double;
};

const collection = [1, 2, 2, 3, 4, 5, 5];
console.log(findDuplicates(collection)); // Результат: [2, 5]
Читайте также
Ретроспектива CSS 2023, что было нового?
Ретроспектива CSS 2023, что было нового?
Ретроспектива CSS 2023, что было нового?

Новинки в 2023 CSS

Стандартизация сигналов в JavaScript
Стандартизация сигналов в JavaScript
Стандартизация сигналов в JavaScript

Подобно Промисам которые прошли стандартизацию Promises TC39 в ES2015 зарождается новый стандарт для управление реактивностью с помощью Signals.

Chrome 121 бета
Chrome 121 бета
Chrome 121 бета

Хром бета доступна с 6 декабря 2023 и последнюю версию можно скачать на официальном сайте Хрома.

18 репозиториев GitHub, которые должен знать каждый разработчик
18 репозиториев GitHub, которые должен знать каждый разработчик
18 репозиториев GitHub, которые должен знать каждый разработчик

Рассказываем о 18 репозиториях GitHub, которые обязательно нужно занести в закладки. Они помогут вам на пути к кодингу.