Сложность: 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.
😎 Решение:
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let m = matrix.count
if m == 0 { return false }
let n = matrix[0].count
var left = 0
var right = m * n - 1
var pivotIdx: Int
var pivotElement: Int
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
}Ставь 👍 и забирай 📚 Базу знаний