Выбор ответа Middle Два указателя обновлено
Слияние в первый массив
Вопрос
Массив a длины m + n содержит m элементов и n пустых мест в конце, b длины n. Слить отсортированно в a без доп. памяти. С какой стороны заполнять?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: С конца: наибольший пишем в позицию m + n - 1. Сзади a свободно, поэтому запись наибольшего в конец ничего не затирает.
Варианты ответа
- С конца: наибольший пишем в позицию m + n - 1правильный ответ
- С начала
a, сдвигая элементы вправо при вставке - Скопировать
bв конецaи вызватьsort - С середины
a, расходясь в обе стороны
Разбор
Сзади a свободно, поэтому запись наибольшего в конец ничего не затирает. Три указателя: на конец данных a, конец b и позицию записи. O(m + n), O(1) памяти.
- С начала пришлось бы сдвигать элементы: O(m · n).
sortдаёт O((m + n) log (m + n)) и не использует отсортированность.- С середины нет смысла: позиции элементов заранее не известны.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.