Yandex контест. Почему выходит «ошибка во время исполнения»?

Question

[space-symbol]

Я всё перепроверил 10 раз, но так и не понял в чём эта ошибка заключается. Надеюсь на вашу помощь

module.exports = function (N, staff, K) {
    if (N === K){
        return staff.reduce((accumulator, currentNumb) => accumulator += currentNumb, 0)
    }
    let maxNumbers = []
    for (let i = 1; i <= K; i++){
        let max = Math.max(...staff)
        maxNumbers.push(max)
        let indexOfMax = staff.indexOf(max)
        staff.splice(indexOfMax, 1)

    }
    return maxNumbers.reduce((accumulator, currentValue) => accumulator += currentValue, 0)
}

Answer 1

[Alexandroppolus]

Тебе надо сумму К самых крупных значений? Решение конечно так себе, O(n*k), я бы поюзал бинарную кучу...

Но если абстрагироваться от скорости, то не разобран кейс, когда К > N. И конечно, переполнение стека при достаточно большом массиве staff. Не используй Math.max(...staff), сделай нормальный человеческий цикл.

N - это ведь длина массива staff?

Comments

[space-symbol]

Да, N - длина массива staff. Я не рассматривал вариант когда K > N т.к по условию такого быть не может, но я на всякий всё же добавлю. А вот как избавиться от переполнение стека я не пока не понимаю

[Alexandroppolus]

space-symbol,

А вот как избавиться от переполнение стека я не пока не понимаю

Говорю же - не писать Math.max(...staff), а например сделать это тем же самым редьюсом. Просто ты в этом выражении поэлементно складываешь весь массив на стек вызовов. А стек не резиновый, и любит скандалить от переполнения.

[Alexandroppolus]

space-symbol, вообще, здесь проще всего отсортировать массив по убыванию и потом посчитать сумму К первых элементов. Это не оптимальный вариант, но он почти наверняка быстрее твоего

[space-symbol]

Alexandroppolus, я так уже переделал и даже перепробовал 4 разные сортировки, включая уже встроенную в язык( sort ), но после 44-го теста я отлетал по времени исполнения.

[space-symbol]

Сергей delphinpro, а я и не думал на него, спасибо, я запомню.

[Alexandroppolus]

space-symbol, с сортировкой не умещается по времени? А с бинарной кучей пробовал? Сортировка даёт O(n*ln(n)), с кучей будет O(n*ln(k))

Кинь ссылку на задачу

[Alexandroppolus]

Хотя можно же за линейное время. Сделай quickselect (загугли что это) для k-го наибольшего по размеру элемента, пусть он окажется равен Р. Далее циклом посчитай сумму всех элементов, которые больше Р, и их количество, это значения S и C.
Ответ равен S + (K - C) * P

[Alexandroppolus]

И кстати, не используй здесь все эти reduce, filter и т.д., они медленные. В алгоритмах - только циклы.

[space-symbol]

Alexandroppolus, ссылку я кинуть не смогу, т.к этот тест был на ограниченное время, но спасибо за проявленную заинтересованность.