Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня43 статьи на LeetCodeСтатья, давайте сегодня рассмотрим 74 вопроса в LeetCode, ищем двумерную матрицу, ищем 2D Matrix.
Официальная сложность этого вопроса — средняя, а процент прохождения — 36%.В отличие от предыдущих вопросов, коэффициент лайков этого вопроса очень высок: 1604 лайка и 154 отказа. Видно, что качество этого вопроса еще очень высокое, и на самом деле это так, вопрос очень интересный.
смысл названия
Смысл этого вопроса также очень прост: учитывая двумерную матрицу массива и целочисленную цель, каждая строка и столбец в этом массиве увеличиваются, и он также удовлетворяетПервый элемент каждой строки больше, чем последний элемент предыдущей строки. Это требует, чтобы мы возвращали логическую переменную, представляющую, находится ли цель в массиве.
То есть это типичная проблема суждения о существовании элементов.Давайте рассмотрим два примера:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
отвечать
Этот вопрос может немного сбить с толку, когда вы впервые задаетесь им. Конечно, мы можем легко увидеть, что этодихотомический вопрос, но два деления, которые мы выполняли ранее, относились к одномерному массиву, а текущие данные двумерные. Как мы их разделим?
Давайте внимательно прочитаем смысл вопроса и снова рассмотрим пример.Легко обнаружить, что если двумерный массив удовлетворяет условию, что каждая строка и столбец упорядочены, и первый элемент каждой строки гарантированно больше, чем последний элемент предыдущей строки, то если мы изменим форму этого 2D-массива на 1D, он все равно будет упорядочен.
Например, есть такой двумерный массив:
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
После преобразования в одно измерение это будет выглядеть так:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
reshape — это термин в numpy, который также можно просто понимать каккаждая строка связана вместе. Поэтому самый простой способ решить эту задачу — уменьшить размерность матрицы до однобитового массива, а затем использовать бинарный метод для определения существования элемента. Если вы ленивы, вы можете использовать numpy для изменения формы.Если вы не знаете numpy, вы можете прочитать мой предыдущий учебник по numpy или вы можете использовать циклы для его обработки самостоятельно.
После перепрошивки он простой двухточечный, сложности вообще нет:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
import numpy as np
arr = np.array(matrix)
# 通过numpy可以直接reshape
arr = arr.reshape((-1, ))
l, r = 0, arr.shape[0]
if r == 0:
return False
# 套用二分
while l+1 < r:
m = (l + r) >> 1
if arr[m] <= target:
l = m
else:
r = m
return arr[l] == target
серьезная практика
Введение numpy reshape предназначено только для того, чтобы предоставить вам решение, которое, очевидно,не хорошая практика. Итак, каким должен быть правильный путь?
Нам все еще нужно провести глубокий анализ проблемы. Думая вперед, кажется, нет никакой подсказки, и мы можем думать назад. Это также обычная процедура для решения задач.Предположим, мы уже знаем, что целевое число существует в матрице, и его номер строки — i, а номер столбца — j. Итак, какие выводы мы можем сделать, исходя из условий вопроса?
Давайте проанализируем соотношение размеров элементов, и мы увидим, что все элементы с номерами строк меньше i меньше его, а все элементы с номерами строк больше i больше его. Элементы одной строки, номер столбца которых меньше j, меньше его, а те, номер столбца которого больше j, больше его.
Это,Строка номер i является невидимой разделительной линией, делит матрицу на две части: та, что выше i, меньше цели, а та, что ниже i, больше цели. Так можем ли мы найти это i пополам?
Здесь очень просто думать, мы можемнайти i по последнему элементу каждой строки. Для двумерного массива последний элемент каждой строки соединяется, образуя одномерный массив, который можно легко разделить на два.
Найдя строку с номером i, мы делаем то же самое и делим строку i, чтобы найти позицию j. Найдя его, оцените, равна ли матрица[i][j] цели, если она равна, то элемент находится в матрице.
Вся идея должна быть хорошо понятна, но в реализации есть небольшая проблема, то есть, когда мы ищем строку, мы ищем позицию первой строки, которая больше или равна цели. То есть мыищем правильную конечную точку, то деление пополам сохраняет интервал, открытый слева и закрытый справа. С точки зрения обработки границ, это противоположно обычно используемому методу записи левого закрытого и правого открытого.Обратив внимание на это, алгоритм может быть реализован плавно:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
if n == 0:
return False
m = len(matrix[0])
if m == 0:
return False
# 初始化，左开右闭，所以设置成-1， n-1
l, r = -1, n-1
while l+1 < r:
mid = (l + r) >> 1
# 小于target的时候移动左边界
if matrix[mid][m-1] < target:
l = mid
else:
r = mid
row = r
# 正常的左闭右开的二分
l, r = 0, m
while l+1 < r:
mid = (l + r) >> 1
if matrix[row][mid] <= target:
l = mid
else:
r = mid
return matrix[row][l] == target
Мы использовали два деления и нашли результат.Каждое деление представляет собой алгоритм O(logN), поэтому целое также является алгоритмом логарифмического уровня.
оптимизация
Нет проблем с алгоритмом выше, но мы сделалидве точки, я чувствую себя немного хлопотно, могу ли я уменьшить его один раз и использовать только одну дихотомию?
Если мы хотим найти ответ, используя только одно деление пополам, то есть мы можем найти способ разделить весь массив, а разделенный массив также имеет отношение размера. Это условие является основанием для использования дихотомии и должно выполняться.
Мы можем легко найти такой атрибут сегментации в массиве, которыйположение элемента. В задаче о матричных элементах одним из часто используемых методов является нумерация элементов в матрице. Например, если точка находится в строке i и столбце j, ее номер равен i * m + j, где m — количество элементов в каждой строке. Это число на самом деле является нижним индексом элемента после сжатия двумерного массива в одно измерение.
Мы можем напрямую разделить это число на два.Определяется диапазон значений числа, который равен [0, mn). Получив число, мы можем восстановить его номера строк и столбцов. А по информации в заголовке мы можем определить, что элементы в этой матрице тоже существуют в порядке возрастания по номеру. Таким образом, мы можем смело использовать дихотомию:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
if n == 0:
return False
m = len(matrix[0])
if m == 0:
return False
l, r = 0, m*n
while l+1 < r:
mid = (l + r) >> 1
# 还原行号和列号
x, y = mid // m, mid % m
if matrix[x][y] <= target:
l = mid
else:
r = mid
return matrix[l // m][l % m] == target
Таким образом, наш код значительно упрощается, а также повышается эффективность работы кода, что быстрее, чем метод с использованием двух двоичных делений.
Суммировать
Этот вопрос здесь закончился.Этот вопрос не сложный, и нетрудно придумать ответ. Но если вы столкнулись с этим на собеседовании, то все равно не так-то просто с первого раза придумать лучшее решение. Это требует от насПолучить опыт, судя по заголовку, вероятно, есть предположение о том, какой тип алгоритма следует использовать.С другой стороны, нам также необходимо иметь достаточное понимание и анализ проблемы, чтобыПрочтите скрытую информацию в заголовке.
Существует также вариант этого вопроса, заключающийся в снятии ограничения, согласно которому первый элемент каждой строки больше, чем последний элемент предыдущей строки. Тогда свойство, что элементы в матрице возрастают в порядке номеров, не существует.Как в такой ситуации мы должны использовать дихотомию? Этот вопрос состоит из 240 вопросов LeetCode.Если вам интересно, вы можете попробовать ответить на этот вопрос, чтобы увидеть, насколько изменилось решение.
Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используется