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

Выполнение задачи будет на 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]
Читайте также
Dev новости: Альтернатива Copilot, Python AI tool, RSC улучшения
Dev новости: Альтернатива Copilot, Python AI tool, RSC улучшения
Dev новости: Альтернатива Copilot, Python AI tool, RSC улучшения

Разработчики не идут в крипту, аналог Copilot, AI && Python, Новый Storybook 8 и подборка новостей

Рассказываем, какие интересные функции появились у веб-браузеров в октябре
Рассказываем, какие интересные функции появились у веб-браузеров в октябре
Рассказываем, какие интересные функции появились у веб-браузеров в октябре

В октябре 2023 года Firefox 118 , Safari 17 и Chrome 117 стали стабильными. Рассказываем, что это значит для веб-платформы.

Dev новости: Deno Decorates, предварительный рендеринг в Nuxt, Astro
Dev новости: Deno Decorates, предварительный рендеринг в Nuxt, Astro
Dev новости: Deno Decorates, предварительный рендеринг в Nuxt, Astro

Прогресс у Deno с JS && TS. релизы Astro и другие новости

В Deno 1.37 улучшили возможности для разработки
В Deno 1.37 улучшили возможности для разработки
В Deno 1.37 улучшили возможности для разработки

Эта интеграция позволяет разработчикам использовать JavaScript и TypeScript в блокнотах Jupyter для анализа данных, машинного обучения и создания интерактивных отчетов.