Search a 2D Matrix
Дана сетка целых чисел matrix с m строками и n столбцами, а также целое число target. Значения в каждой строке отсортированы по возрастанию, а первое значение каждой строки больше последнего значения предыдущей строки. Верните true, если target присутствует в сетке, и false в противном случае, за время O(log(m × n)).
Функция
- matrixinteger-2d-array
- сетка, заданная в виде списка строк, отсортированных построчно
- targetinteger
- значение, которое нужно найти
- Возвращаетboolean
- true, если цель находится в сетке, false в противном случае
Ограничения
1 ≤ m, n ≤ 100, гдеm = matrix.lengthиn = matrix[i].length- Каждая строка имеет одинаковую длину
n. -104 ≤ matrix[i][j], target ≤ 104- Каждая строка отсортирована в строго возрастающем порядке, и первое значение каждой строки больше последнего значения предыдущей строки.
Примеры
- Ввод
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Вывод
- true
- Пояснение
- Если читать построчно, 12 значений образуют один отсортированный список. При двоичном поиске по позициям от 0 до 11 проверяется 21 на позиции 5 (слишком мало), 33 на позиции 8 (слишком много), затем находится 26 на позиции 6.
- Ввод
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Вывод
- false
- Пояснение
- 16 шло бы после 14, последнего значения строки 0, и перед 17, первым значением строки 1. Между ними ничего нет, поэтому 16 отсутствует в сетке.
Дополнительный вопрос
Предположим, строки могут иметь разную длину, но при этом оставаться отсортированными от начала до конца. Как преобразовать позицию в номер строки и столбца и какова будет стоимость поиска?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Читайте матрицу строка за строкой, слева направо, как если бы это был один длинный список. Что вы замечаете в порядке значений в этом списке?
Вместе эти два правила означают, что вся матрица, прочитанная по строкам, представляет собой один отсортированный список из
m × nзначений. В нём можно выполнить бинарный поиск, даже не создавая этот список.Выполняйте двоичный поиск по позициям от
0доm × n - 1. Позицияpнаходится в строкеp / nи столбцеp % n(целочисленное деление), поэтому на каждом шаге считывается одна ячейка и отбрасывается половина оставшихся позиций.
Решение
Два правила упорядочивания вместе превращают сетку, прочитанную построчно, в один отсортированный список из m × n значений. Выполните бинарный поиск в этом списке по позиции и восстановите строку и столбец для каждой позиции с помощью одного деления. Тогда для сетки размером 100 на 100 потребуется не более 14 сравнений вместо 10000.
Проверьте каждую ячейку
Идея
Сравнивайте каждую ячейку с target и возвращайте true при совпадении, false после последней ячейки. Алгоритм проверяет каждую ячейку, поэтому подходит для любой сетки, отсортированной или нет. Он никогда не использует порядок, поэтому сетка размером 100 на 100 требует до 10000 сравнений.
Алгоритм
- Для каждой строки
matrixпоследовательно проверьте каждое значение. - Если значение равно
target, вернитеtrue. - После циклов верните
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseИдите от верхнего правого угла
Идея
Начиная с ячейки в правом верхнем углу, каждое значение слева меньше, а каждое значение ниже больше. Если значение в ячейке больше, чем target, то и значения в столбце под ней больше: шагни влево и исключи этот столбец. Если оно меньше, то и значения в строке слева меньше: шагни вниз и исключи эту строку.
В первом примере 14 меньше 26, поэтому шагни вниз к 30. 30 больше, поэтому шагни влево к 26 — совпадение. Каждый шаг исключает строку или столбец, поэтому потребуется не более m + n шагов: 200 для сетки размером 100 на 100. Для этого обхода достаточно, чтобы строки и столбцы были отсортированы, поэтому он использует лишь половину информации, которую дает эта сетка.
Алгоритм
- Начните со строки
0и последнего столбца. - Пока строка и столбец находятся внутри сетки, прочитайте ячейку.
- Если она равна
target, вернитеtrue. - Если значение больше, переместитесь на один столбец влево; если меньше — на одну строку вниз.
- Когда выйдете за пределы сетки, верните
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
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 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return FalseБинарный поиск по плоской сетке
Идея
Пронумеруй ячейки по строкам: в строке 0 находятся позиции от 0 до n - 1, в строке 1 — от n до 2n - 1 и так далее. Каждая строка отсортирована и начинается выше того места, где закончилась предыдущая, поэтому значения только увеличиваются с ростом позиции. Это отсортированный список, и к нему можно применить бинарный поиск.
Сам список создавать не нужно. Позиция p находится в строке p / n и столбце p % n, если использовать целочисленное деление. В первом примере n = 4, поэтому позиция 6 — это строка 1, столбец 2, где находится 26. При каждом сравнении количество позиций, в которых может находиться target, сокращается вдвое: для 10000 ячеек понадобится не более 14 сравнений, при использовании двух индексов дополнительной памяти.
Алгоритм
- Пусть
mиn— количество строк и столбцов, аlo = 0иhi = m × n - 1. - Пока
lo ≤ hi, найдитеmidпосередине между ними. - Прочитайте
value = matrix[mid / n][mid % n]. - Если
valueравноtarget, вернитеtrue. Если оно меньше, установитеlo = mid + 1; в противном случае установитеhi = mid - 1. - Когда цикл завершится, верните
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
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
Ловушки и крайние случаи
- Деление на количество строк вместо количества столбцов. Позиция
pнаходится в строкеp / n; если использовать вместо негоm, код проходит проверку на квадратных сетках и дает сбой на сетках из 3 строк и 4 столбцов. - В версии с двумя поисками не обрабатывается случай, когда
targetменьшеmatrix[0][0]. Ни одна строка не начинается с этого значения или ниже, и индекс строки-1попадает во второй поиск. - Цикл с условием
lo < hiпри включительномhi. Сетка 1 на 1, содержащаяtarget, возвращаетfalse, потому что цикл ни разу не выполняется. - В Lua и R забывают о переходе к индексации с 1: позиция
p— это строкаp / n + 1, столбецp % n + 1.
Частые вопросы3
Какова временная сложность поиска в двумерной матрице?
Бинарный поиск по уплощённой сетке выполняется за время O(log(m × n)) и использует O(1) памяти: не более 14 сравнений для 10000 ячеек. Поскольку log(m × n) = log m + log n, по эффективности он соответствует поиску строки, а затем элемента внутри неё.
Стоит ли использовать обход из верхнего правого угла или бинарный поиск?
Обход по углам занимает O(m + n) шагов и требует только сортировки строк и столбцов, поэтому он также решает вариант, в котором строка может начинаться ниже конца предыдущей строки. Когда каждая строка начинается выше того места, где заканчивается предыдущая, как здесь, бинарный поиск работает быстрее.
Верно ли также использовать два бинарных поиска: один для строки, а другой внутри неё?
Да. Выполните бинарный поиск в первом столбце, чтобы найти последнюю строку, первое значение которой не превышает target, а затем выполните бинарный поиск в этой строке. Сложность составляет O(log m + log n) — такая же асимптотическая оценка. Один поиск выполняет ту же работу с одним циклом и меньшим количеством граничных случаев.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def searchMatrix(matrix, target):
# Напишите код здесьТест #1
Тест #2
Аргументы
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Ожидаемый вывод
true