Search a 2D Matrix

Средняя№74найти число

Дана матрица: каждая строка отсортирована, и каждая начинается с числа больше последнего числа строки выше. Нужно сказать, есть ли в ней искомое число, за O(log(строки · столбцы)). Наш пример: матрица 3 × 4 ниже и 26 — ответ true.

74 Search a 2D MatrixРазбор · 1×

Пример: Строки [2, 4, 7, 9], [12, 15, 18, 20], [23, 26, 30, 34], ищем 26. Сверху те же числа, прочитанные строка за строкой как один список из 12.

0214273941251561872082392610301134012302479112151820223263034
ещё в диапазонесередина, проверяемотброшенонайдено

В строке 4 числа: cols = 4

01/26
сначала · назад · пуск · шаг
Скорость
1function searchMatrix(matrix, target):
2 cols = len(matrix[0])
3 lo = 0
4 hi = len(matrix) * cols - 1
5 while lo <= hi:
6 mid = floor((lo + hi) / 2)
7 value = matrix[floor(mid / cols)][mid mod cols]
8 if value == target:
9 return true
10 if value < target:
11 lo = mid + 1
12 else:
13 hi = mid - 1
14 return false
состояние
cols
4
lo
–
hi
–
mid
–
value
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждая строка отсортирована и начинается выше конца предыдущей, поэтому строки, прочитанные одна за другой, — это один отсортированный список из строки · столбцы чисел.
  2. Бинарный поиск идёт по индексам этого списка, не собирая его: индекс k — это строка floor(k / cols), столбец k mod cols. Здесь mid = 8 попадает на 23 — первое число строки 2.
  3. Один поиск по всем клеткам занимает около log(строки · столбцы) шагов, столько же, сколько найти сначала строку, а потом искать внутри неё.

Сложность

Время O(log(m · n)) для m строк и n столбцов: каждый шаг делит диапазон клеток пополам. Память O(1): матрица в список не копируется.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.