Выбор ответа Middle Два указателя обновлено
Удаление дубликатов на месте
Вопрос
Удаляем дубликаты из отсортированного массива на месте. Какой инвариант держит указатель w?
let w = 1;
for (let r = 1; r < arr.length; r++) {
if (arr[r] !== arr[w - 1]) arr[w++] = arr[r];
}
// новая длина = w
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: arr[0..w) содержит уникальные элементы в исходном порядке. Медленный указатель w указывает, куда писать следующий уникальный элемент; всё левее него уже готовый ответ.
Варианты ответа
arr[w]всегда равен максимуму уже просмотренной частиarr[0..w)содержит уникальные элементы в исходном порядкеправильный ответwвсегда равенr - 1, то есть отстаёт ровно на одинarr[w..]отсортирован по убыванию после каждого шага
Разбор
Медленный указатель w указывает, куда писать следующий уникальный элемент; всё левее него уже готовый ответ. Быстрый r читает. Пишем, только если arr[r] !== arr[w - 1]. Итог O(n) времени, O(1) памяти.
- Максимум тут ни при чём.
wотстаёт отrна число найденных дубликатов, не всегда на 1.- Хвост массива после
wне важен и не упорядочен по убыванию.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.