Сложность: 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.
😎 Решение:
var searchMatrix = function (matrix, target) {
let m = matrix.length;
if (m == 0) return false;
let n = matrix[0].length;
let left = 0,
right = m * n - 1;
let pivotIdx, pivotElement;
while (left <= right) {
pivotIdx = Math.floor((left + right) / 2);
pivotElement = matrix[Math.floor(pivotIdx / n)][pivotIdx % n];
if (target == pivotElement) return true;
else {
if (target < pivotElement) right = pivotIdx - 1;
else left = pivotIdx + 1;
}
}
return false;
};Ставь 👍 и забирай 📚 Базу знаний