Алгоритми та структури даних · Middle · Запитання 72 з 75
Що робить ця функція і яка в неї складність?
function f(nums) {
const seen = new Set(nums);
let best = 0;
for (const x of seen) {
if (seen.has(x - 1)) continue;
let len = 1;
while (seen.has(x + len)) len++;
best = Math.max(best, len);
}
return best;
}- ✓Правильна відповідь: Найдовша серія послідовних чисел, O(n)
- 2Кількість дублікатів, O(n²)
- 3Найбільше число в масиві, O(n log n)
Пояснення
Серію рахують лише від її найменшого числа (коли x - 1 відсутнє), тож кожне число перевіряється у внутрішньому циклі щонайбільше раз. Сортування дало б O(n log n).