Выбор ответа Junior Массивы и хеш-таблицы спрашивают часто обновлено
Есть ли дубликат
Вопрос
Что вернёт функция для [3, 1, 4, 1] и какая у неё сложность?
function hasDup(arr) {
const seen = new Set();
for (const x of arr) {
if (seen.has(x)) return true;
seen.add(x);
}
return false;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: true, O(n). Встретив вторую 1, seen.has(1) даст true.
Варианты ответа
false, O(n)true, O(n)правильный ответtrue, O(n²)true, O(n log n)
Разбор
Встретив вторую 1, seen.has(1) даст true. Один проход, Set.has и Set.add O(1) в среднем: O(n) времени, O(n) памяти.
falseневерно: дубликат есть.- O(n²) было бы с
includesвнутри цикла. - O(n log n) было бы с сортировкой и сравнением соседей.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.