Где применяется
1. Задача
У тебя есть сетка чисел, и числа в ней стоят по порядку. В каждой строке они растут слева направо. В каждом столбце они растут сверху вниз. Тебе дают искомое число, и надо ответить на один вопрос: есть оно в сетке или нет?
Проще всего посмотреть на каждую клетку. Но в большой сетке это медленно. Порядок чисел помогает пропустить почти все клетки и дойти до ответа одной короткой дорожкой.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитsearchMatrix([[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], 14)| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 4 | 7 | 11 | 15 |
| 1 | 2 | 5 | 8 | 12 | 19 |
| 2 | 3 | 6 | 9 | 16 | 22 |
| 3 | 10 | 13 | 14 | 17 | 24 |
| 4 | 18 | 21 | 23 | 26 | 30 |
Есть ли 14 в матрице? Начинаем с правого верхнего угла: слева от него всё меньше, снизу всё больше.
Столбики: 48 ячеек таблицы, ряд за рядом; каждый ряд и каждый столбец возрастают. Искомое число в нижнем ряду. В таблице ниже n означает число ячеек квадратной таблицы.
Одна операция: одна проверенная ячейка. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(m·n)O(m + n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- матрица отсортирована и по строкам, и по столбцам
- поиск значения в 2D отсортированной сетке
- начать с угла и отбрасывать строку или столбец
- и строки, и столбцы монотонны
Похоже, но не то
- Бинарный поиск (массив) (Binary search (array))
Если каждый ряд продолжает предыдущий, сетка это один отсортированный список. Тогда работает обычный бинарный поиск.
- Два указателя (с концов) (Two pointers (opposite ends))
Ход лесенкой это та же идея в двух измерениях. За шаг двигается ровно один индекс.
- Обход матрицы (спираль / диагонали) (Matrix traversal (spiral / diagonal))
Там посещается каждая клетка в выбранном порядке. Здесь большинство клеток не читается вовсе.
- Линейный поиск (Linear search)
Перебор работает и стоит O(rc). Расточительным его делает как раз наличие порядка.
Сетка r на c даёт O(r + c) при ходе лесенкой. Полностью отсортированная сетка позволяет O(log rc).
На LeetCode
Задачи на сетку, где отсортированы и строки, и столбцы, и спрашивают, есть ли значение или сколько значений лежит ниже какой-то границы. Начни с правого верхнего угла, и каждое сравнение отбрасывает строку или столбец, это O(rows + cols).
Задача урока слово в слово.
Строки и столбцы убывают, так что начни с правого верхнего угла, шагай влево, пока значение отрицательное, и для каждой строки прибавляй отрицательные справа от тебя.
Каждая строка начинается выше конца предыдущей, так что обход от угла работает, а бинарный поиск по всем клеткам как по одному списку быстрее.
Бинарный поиск по значению, и для каждой догадки считай клетки не больше неё обходом от угла за O(n).