Эта задача похожа на «Поиск в 2D матрице», решение которой я написал в своей предыдущей статье. Если вы читали предыдущую статью, прочтите описание проблемы и переходите к эффективному решению.
Ссылка на проблему
Описание проблемы:
Напишите эффективный алгоритм, который ищет значение target в целом числе m x n matrix. matrix имеет следующие свойства:
- Целые числа в каждой строке сортируются по возрастанию слева направо.
- Целые числа в каждом столбце сортируются по возрастанию сверху вниз.
Наивное решение:
Обход каждого элемента в матрице и сравнение его с целевым значением. Временная сложность O(mn), что очень неэффективно.
Достойное решение:
Поскольку каждая строка отсортирована, мы можем использовать бинарный поиск для поиска каждой строки. Временная сложность этого решения составляет O(nlogm). logm — это время, необходимое для двоичного поиска в строке, и, поскольку мы делаем это для каждой строки, O (n * logm) — это общая временная сложность.
Эффективное решение:
Предложенное выше решение O(nlogm) является достойным решением, но мы можем дополнительно его оптимизировать. Нам не нужно проходить каждую строку. В вопросе говорится, что целые числа в каждом столбце также отсортированы.
Итак, из примеров, если вы внимательно посмотрите, элемент в правом верхнем углу имеет все элементы меньше, чем он, слева от него, и все элементы больше, чем он, в его нисходящем направлении.
- Начните с верхнего правого
- Если цель меньше, чем верхний правый элемент, двигайтесь влево, так как мы можем игнорировать этот столбец.
- Если цель больше, чем верхний правый элемент, двигаться вниз, так как мы можем игнорировать эту строку
В примере 1 15 — это элемент в правом верхнем углу.
- [1,4,7,11] находятся слева от 15, которые меньше его.
- [19,22,24,30] расположены в нисходящем направлении и больше 15.
- Целевой элемент равен 5, что меньше 15. Итак, мы движемся влево.
- Теперь 5‹11, снова влево
- Теперь 5‹7, снова влево
- Теперь 5>4, двигаться вниз
- Доходим до целевого элемента 5.
Временная сложность — O(m+n).
