Получение элементов, которые имеют более одной записи в массиве с оптимизированным кодом

let array = [1,7,2,2,3,7,4];
    
    while(array.length){
        // get last item
        let item = array.pop()
        
        // remove duplicates
        const filteredArray = array.filter(content => content!==item);
        
        // if filteredArray had duplicate items then log the item
        if ( filteredArray.length !== array.length) console.log(item)

        array = filteredArray

    }

Этот код предназначен для поиска элементов с повторяющимися записями. Оптимизирован ли этот код и какова его сложность или время выполнения.

есть ли лучший способ сделать это, я действительно застрял в понимании того, как определить сложность

Сложность времени рассчитывается как условие наихудшего случая:

Здесь цикл while может повторять «n» раз максимум (случай, когда нет повторяющихся элементов)

каждый оператор внутри цикла while ожидать array.filter имеет сложность 0 (1) поэтому мы можем игнорировать его (потому что это просто постоянные линейные операции, поэтому сложность всегда равна 0 (1))

В то время как array.filter как временная сложность 0 (n-1) [After removing last item] который после удаления констант становится 0 (n)

поэтому общая временная сложность этого уравнения становится (в то время как сложность цикла * сложность фильтра), поскольку они являются операцией вложенного цикла

поэтому окончательный ответ — 0 (n ^ 2)

Также мы должны учитывать космическая сложность .

в рассматриваемом решении есть прерывистая переменная filterArray, которая будет иметь максимальную длину «n» (в случае отсутствия повторяющихся элементов), поэтому сложность пространства равна 0 (n) (поскольку ей требуется место в памяти для каждого элемента в массиве )

поэтому общая сложность пространства будет

array (0(n)) + item(0(1)) + filteredArray(0(n)) = 0(n)

Лучшее решение:

    const arry = [1,7,2,2,3,7,4];
    
    const toFindDuplicates = arry => arry.filter((item, index, arr) => arr.indexOf(item) !== index)
    const duplicateElements = toFindDuplicates(arry);
    console.log(duplicateElements);

Имеет временную сложность О (п ^ 2) благодаря функциям indexof и filter

Космическая сложность

здесь tofindDuplicates — это функция, поэтому 0 (1), duplicateElements будет иметь максимум n / 2 дубликатов

array (0(n)) + toFindDuplicates 0(1) + duplicateElements  (0(n/2)) = 0(n)

Лучший подход:

array = [1, 7, 2, 2, 3, 7, 4]
array.sort(function (a, b) {
    return a - b;
});

const duplicateEntries = array.filter((element, index, array) => {
    if (index !== 0) {
        const nextElement = array[index + 1]
        const previousElement = array[index - 1]
        return nextElement !== element && previousElement === element
    }
})

console.log(duplicateEntries)

Здесь временная сложность

array.sort(nlog(n)) + filter(n) = O(n)+O(nlogn) = O(nlogn)

космическая сложность составляет:

O(n/2) = O(n) which is the worst for duplicate entries