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

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

    }

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

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

1 ответ
1

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

Здесь цикл 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

  • 1

    Приведенный вами фрагмент кода – $ O (n ^ 2) $ not $ O (n) $, потому что у вас есть indexOf внутри фильтра, который должен перебирать массив, чтобы найти дубликат, поэтому, если нет дубликатов для каждого элемента, вы проверяете каждый элемент на совпадение. Вы можете использовать set чтобы функция $ O (n) ( $ eg const a = new Set(), dups = []; array.forEach(item => a.has(item) ? dups.push(item) : a.add(item)); console.log(dups); // >> array of duplicated items

    – Слепой67

  • @ Blindman67 большое спасибо, поэтому и вопрос, и ответ имеют одинаковую временную сложность? нет ли дополнительного преимущества, чем космическая сложность для подхода в ответ?

    – PDСкрыть

  • @ Blindman67 спасибо за помощь, обновил ответ

    – PDСкрыть

  • ответ, который вы упомянули, не работает

    – PDСкрыть

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *