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