Поиск в отсортированной матрице: Search a 2D Matrix I и II, k-й наименьший
Как искать в отсортированной матрице: бинпоиск по «развёрнутому» массиву, поиск от угла лесенкой за O(m+n) и k-й наименьший элемент через бинпоиск по ответу. Код на Python.
Коротко
| Задача | Как отсортирована матрица | Приём | Время |
|---|---|---|---|
| Search a 2D Matrix (LeetCode 74) | строки по возрастанию, каждая строка начинается больше, чем кончилась предыдущая | обычный бинпоиск по индексу | |
| Search a 2D Matrix II (LeetCode 240) | строки и столбцы по возрастанию, порядка между строками нет | лесенка от правого верхнего угла | |
| Kth Smallest Element in a Sorted Matrix (LeetCode 378) | как в задаче 240, матрица | бинпоиск по значению + подсчёт лесенкой |
- Сначала выясните, какая сортировка у матрицы. От этого зависит всё решение, и это первый вопрос, который стоит задать интервьюеру.
- Матрица из задачи 74 — это просто отсортированный массив, разрезанный на строки. Ищем в ней как в массиве.
- В матрице из задачи 240 из правого верхнего угла каждое сравнение отбрасывает целую строку или целый столбец.
- Та же лесенка за считает, сколько элементов не больше . Отсюда k-й наименьший через бинпоиск по ответу.
Два вида «отсортированных» матриц
Фраза «матрица отсортирована» на собеседовании может значить разное. Сравните:
Задача 74 Задача 240
1 3 5 7 1 4 7 11 15
10 11 16 20 2 5 8 12 19
23 30 34 60 3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
Слева, если читать построчно, получится сплошной отсортированный массив: 1 3 5 7 10 11 …. Справа каждая строка и каждый столбец возрастают, но строки перекрываются: во второй строке есть 2, хотя первая доходит до 15. Построчно такая матрица не отсортирована.
Решение для правой матрицы работает и для левой, но медленнее, чем могло бы. Решение для левой на правой просто ломается. Поэтому спросите, гарантировано ли, что первый элемент строки больше последнего элемента предыдущей.
Search a 2D Matrix: матрица как один массив
Условие: матрица , строки отсортированы, первый элемент каждой строки больше последнего элемента предыдущей. Есть ли в ней target?
Перебор и бинпоиск по строкам
Перебор всех клеток — , он не использует сортировку вообще. Бинарный поиск в каждой строке — , уже лучше, но тоже не оптимально: мы игнорируем порядок между строками.
Бинпоиск по виртуальному массиву
Пронумеруем клетки построчно: клетка (r, c) получает индекс r * n + c. Обратное преобразование: индекс i — это строка i // n и столбец i % n. По условию значения по этим индексам идут по возрастанию, значит работает обычный бинарный поиск на отрезке , только вместо arr[mid] читаем клетку матрицы.
def search_matrix_1(matrix, target): if not matrix or not matrix[0]: return False rows, cols = len(matrix), len(matrix[0]) lo, hi = 0, rows * cols - 1 while lo <= hi: mid = (lo + hi) // 2 value = matrix[mid // cols][mid % cols] if value == target: return True if value < target: lo = mid + 1 else: hi = mid - 1 return False m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] print(search_matrix_1(m, 3)) # True print(search_matrix_1(m, 13)) # False
Время , память . Матрицу никуда не копируем: «развёрнутый» массив существует только в формуле индекса.
Самая частая ошибка здесь — делить на число строк вместо числа столбцов: mid // rows. На квадратной матрице тесты проходят, на прямоугольной — нет. Строка индекса определяется тем, сколько полных строк длины cols до него поместилось.
Вариант: два бинпоиска
Можно рассуждать иначе: сначала бинпоиском по первому столбцу найти последнюю строку, которая начинается с числа не больше target, потом бинпоиском искать в ней.
from bisect import bisect_left, bisect_right def search_matrix_1_two_steps(matrix, target): if not matrix or not matrix[0]: return False
# первый столбец: ищем последнюю строку, которая начинается с <= target
first = [row[0] for row in matrix]
r = bisect_right(first, target) - 1
if r < 0:
return False
row = matrix[r]
c = bisect_left(row, target)
return c < len(row) and row[c] == target
Асимптотика та же: $O(\log m + \log n)$. Строчка `first = [...]` в этой версии стоит $O(m)$ — для чистоты можно искать по первому столбцу вручную, без копирования. Плюс этого варианта в том, что он естественно обобщается на случай, когда строки разной длины: развернуть такую матрицу в один индекс уже не получится.
## Search a 2D Matrix II: поиск лесенкой
Условие: каждая строка возрастает слева направо, каждый столбец — сверху вниз. Есть ли в матрице `target`?
Развернуть в массив больше нельзя. Бинпоиск по каждой строке даёт $O(m \log n)$. Есть решение проще и быстрее.
### Почему правый верхний угол
Посмотрим на правый верхний элемент `15`. Он **самый большой в своей строке** и **самый маленький в своём столбце**. Это единственный угол (вместе с левым нижним) с таким свойством, и именно оно даёт однозначное решение на каждом шаге:
- если `matrix[r][c] > target`, то весь столбец `c` ниже текущей клетки ещё больше. Столбец можно выбросить: `c -= 1`;
- если `matrix[r][c] < target`, то вся строка `r` левее текущей клетки ещё меньше. Строку можно выбросить: `r += 1`;
- если равно — нашли.
Из левого верхнего угла так не получится: там элемент меньше всех и в строке, и в столбце. Если он меньше `target`, непонятно, куда идти — вправо или вниз. Так же бесполезен правый нижний угол.
```python
def search_matrix_2(matrix, target):
if not matrix or not matrix[0]:
return False
r, c = 0, len(matrix[0]) - 1 # правый верхний угол
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # весь столбец c ниже ещё больше
else:
r += 1 # вся строка r левее ещё меньше
return False
m = [
[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],
]
print(search_matrix_2(m, 5)) # True
print(search_matrix_2(m, 20)) # False
Разбор: ищем 14
| Шаг | Клетка | Значение | Решение |
|---|---|---|---|
| 1 | (0, 4) | 15 | 15 > 14, выбрасываем столбец 4 |
| 2 | (0, 3) | 11 | 11 < 14, выбрасываем строку 0 |
| 3 | (1, 3) | 12 | 12 < 14, выбрасываем строку 1 |
| 4 | (2, 3) | 16 | 16 > 14, выбрасываем столбец 3 |
| 5 | (2, 2) | 9 | 9 < 14, выбрасываем строку 2 |
| 6 | (3, 2) | 14 | нашли |
Путь идёт лесенкой: только влево и вниз. Отсюда и название — staircase search.
Почему это корректно и сколько стоит
Инвариант: если target есть в матрице, он лежит в прямоугольнике «строки от r до конца, столбцы от 0 до c». В начале это вся матрица. Каждый шаг выбрасывает строку или столбец, в которых target быть не может, — это мы показали выше. Когда прямоугольник опустел (r == m или c < 0), элемента нет.
На каждом шаге либо r растёт, либо c уменьшается. Всего шагов не больше , время , память .
Сравним с бинпоиском по строкам. Для квадратной матрицы лесенка делает до 2000 шагов, бинпоиск по строкам — около сравнений. Но если матрица очень вытянутая, например , бинпоиск по 10 строкам даёт около 200 сравнений, а лесенка может пройти миллион шагов. На собеседовании стоит упомянуть: «для квадратной матрицы лесенка лучше, для сильно вытянутой — бинпоиск по коротким строкам». Это хороший сигнал, что вы думаете о входных данных, а не заучили ответ.
Для квадратной матрицы быстрее в худшем случае нельзя: все элементов побочной диагонали могут быть никак не связаны между собой порядком, и каждый придётся проверить.
То же решение на JavaScript:
function searchMatrix(matrix, target) { if (matrix.length === 0 || matrix[0].length === 0) return false let r = 0 let c = matrix[0].length - 1 while (r < matrix.length && c >= 0) { const value = matrix[r][c] if (value === target) return true if (value > target) c-- else r++ } return false }
Где ещё работает лесенка
Лесенка — это по сути два указателя, только по двум измерениям матрицы. Она подходит всюду, где нужно посчитать или найти что-то относительно порога.
Count Negative Numbers in a Sorted Matrix (LeetCode 1351): матрица не возрастает по строкам и столбцам, посчитать отрицательные. Идём из левого нижнего угла. Если клетка отрицательная, отрицательны и все клетки правее неё в этой строке: прибавляем их число и поднимаемся. Иначе сдвигаемся вправо.
def count_negatives(grid): rows, cols = len(grid), len(grid[0]) r, c = rows - 1, 0 total = 0 while r >= 0 and c < cols: if grid[r][c] < 0: total += cols - c r -= 1 else: c += 1 return total print(count_negatives([[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]])) # 8
Это вместо перебора. Самая полезная разновидность лесенки — подсчёт элементов, не превосходящих . На ней держится следующая задача.
K-й наименьший элемент в отсортированной матрице
Условие LeetCode 378: квадратная матрица , строки и столбцы отсортированы по возрастанию. Найти k-й по величине элемент в порядке сортировки (с повторами, а не k-й различный).
1 5 9
10 11 13 k = 8 → 13
12 13 15
Все элементы по порядку: 1 5 9 10 11 12 13 13 15. Восьмой — 13.
Решение 1: собрать и отсортировать
Сложить все элементов в список и отсортировать — времени и памяти. Работает, но не использует структуру матрицы, а условие задачи прямо просит память лучше .
Решение 2: куча, как в слиянии k списков
Каждая строка — отсортированный список. Значит, это задача слияния k отсортированных списков: кладём в кучу первые элементы строк, раз достаём минимум и добавляем следующий элемент той же строки.
import heapq def kth_smallest_heap(matrix, k): n = len(matrix) heap = [(matrix[r][0], r, 0) for r in range(min(n, k))] heapq.heapify(heap) for _ in range(k - 1): value, r, c = heapq.heappop(heap) if c + 1 < n: heapq.heappush(heap, (matrix[r][c + 1], r, c + 1)) return heap[0][0] print(kth_smallest_heap([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)) # 13
Строк больше брать не нужно: k-й элемент заведомо найдётся среди первых строк. Время , память . При порядка это — не лучше сортировки по времени, но память уже .
Решение 3: бинпоиск по ответу
Вместо того чтобы искать позицию, будем искать значение. Обозначим — сколько элементов матрицы не больше . Эта функция не убывает по . Ответ — наименьшее , при котором .
Монотонный предикат на отрезке значений — классическая постановка бинпоиска по ответу. Ищем на отрезке : это минимум и максимум матрицы.
Осталось быстро считать . Это та же лесенка, только из левого нижнего угла:
- если
matrix[r][c] <= x, то и все элементы столбцаcвыше него не большеx. Прибавляемr + 1и идём вправо; - иначе этот элемент и всё правее в строке больше
x. Поднимаемся на строку вверх.
def count_less_equal(matrix, x): n = len(matrix) r, c = n - 1, 0 # левый нижний угол count = 0 while r >= 0 and c < n: if matrix[r][c] <= x: count += r + 1 # весь столбец c до строки r включительно c += 1 else: r -= 1 return count def kth_smallest(matrix, k): lo, hi = matrix[0][0], matrix[-1][-1] while lo < hi: mid = (lo + hi) // 2 if count_less_equal(matrix, mid) >= k: hi = mid else: lo = mid + 1 return lo print(kth_smallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)) # 13
Разбор на примере
Матрица выше, , отрезок .
lo | hi | mid | Решение | |
|---|---|---|---|---|
| 1 | 15 | 8 | 2 (1, 5) | , lo = 9 |
| 9 | 15 | 12 | 6 (1, 5, 9, 10, 11, 12) | , lo = 13 |
| 13 | 15 | 14 | 8 | , hi = 14 |
| 13 | 14 | 13 | 8 | , hi = 13 |
lo == hi == 13 — ответ.
Почему ответ обязательно есть в матрице
Частый вопрос интервьюера: мы перебираем значения из отрезка, а не элементы матрицы. Вдруг найдём число, которого в матрице нет?
Не найдём. Бинпоиск возвращает наименьшее с . Пусть не встречается в матрице. Тогда элементов, не больших , ровно столько же, сколько не больших : . Значит, не наименьшее — противоречие. Для целых чисел этого достаточно.
Если в матрице дробные числа, бинпоиск по значению тоже работает, но остановить его надо по точности, а ответ потом «прижать» к ближайшему элементу матрицы, не превосходящему найденное значение. На LeetCode матрица целочисленная, так что этот случай обычно не спрашивают.
Сложность
Подсчёт — (лесенка на шагов). Бинпоиск делает итераций. Итого времени и памяти. При значениях до это около 30 проходов лесенки — для меньше 20 000 операций против полутора миллионов у сортировки.
Существует и алгоритм Фредериксона–Джонсона, который находит k-й элемент в такой матрице за , но на собеседованиях его не ждут: он заметно сложнее и почти не встречается в разборах.
Та же идея без матрицы
Kth Smallest Number in Multiplication Table (LeetCode 668): таблица умножения , где в клетке стоит . Хранить её не нужно: строка — это числа , и в ней не больше ровно элементов.
def find_kth_number(m, n, k): lo, hi = 1, m * n while lo < hi: mid = (lo + hi) // 2 count = sum(min(mid // i, n) for i in range(1, m + 1)) if count >= k: hi = mid else: lo = mid + 1 return lo print(find_kth_number(3, 3, 5)) # 3
Время . Тот же каркас решает Find K-th Smallest Pair Distance (LeetCode 719): сортируем массив, а пары с расстоянием не больше считаем двумя указателями.
Сводная таблица
| Задача | Наивно | Оптимально | Память |
|---|---|---|---|
| 74, строки «продолжают» друг друга | , бинпоиск по индексу | ||
| 240, строки и столбцы отсортированы | , лесенка | ||
| 1351, подсчёт отрицательных | , лесенка | ||
| 378, k-й наименьший | , бинпоиск + лесенка | ||
| 668, таблица умножения |
Типичные ошибки
- Решение задачи 74 на матрице из задачи 240. Бинпоиск по развёрнутому индексу на матрице, где строки перекрываются, пропустит элементы. Сначала уточните условие.
mid // rowsвместоmid // cols. На квадратных тестах ошибка не видна.- Лесенка из левого верхнего угла. Оттуда нет однозначного хода. Только правый верхний или левый нижний.
- Пустая матрица.
[]и[[]]— разные случаи: во второмlen(matrix[0])равен нулю, иcстартует с-1. Проверкаif not matrix or not matrix[0]закрывает оба. count > kвместоcount >= kв бинпоиске по ответу. При повторяющихся значениях (две13в примере) получится ответ больше правильного. Ищем наименьшее , при котором элементов не меньше .- Возврат
midвместоlo. В шаблонеwhile lo < hiответ — этоloпосле выхода из цикла. - Переполнение
(lo + hi) / 2в Java и C++ при отрицательных и больших значениях. Пишитеlo + (hi - lo) / 2. В Python проблемы нет, но про неё полезно сказать вслух.
Как подавать на собеседовании
- Уточните тип сортировки матрицы и размеры: квадратная ли, бывают ли пустые строки, есть ли повторы.
- Назовите перебор за одной фразой и сразу переходите к структуре.
- Для задачи 74 скажите «это отсортированный массив, нарезанный на строки» и напишите бинпоиск с формулой индекса.
- Для задачи 240 объясните, почему именно правый верхний угол: он максимум строки и минимум столбца. Затем инвариант и оценка .
- Для k-го наименьшего начните с кучи — её легко написать и легко обосновать. Затем предложите бинпоиск по значению и объясните, почему ответ всегда элемент матрицы.
Близкие темы на сайте: поиск в повёрнутом отсортированном массиве — ещё одна задача, где бинпоиск работает на «почти» отсортированных данных, и спиральный обход матрицы, если нужно потренировать аккуратную работу с индексами.