Сложность: medium
Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:
Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.
Вы должны написать решение с временной сложностью O(log(m * n)).
Пример:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
👨💻 Алгоритм:
1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.
2⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.
3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.
😎 Решение:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) return false;
int n = matrix[0].length;
int left = 0, right = m * n - 1;
int pivotIdx, pivotElement;
while (left <= right) {
pivotIdx = (left + right) / 2;
pivotElement = matrix[pivotIdx / n][pivotIdx % n];
if (target == pivotElement) return true;
else {
if (target < pivotElement) right = pivotIdx - 1;
else left = pivotIdx + 1;
}
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний