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

Выполнение задачи будет на 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]