Сложность: medium
Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.
Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.
Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.
Пример:
Input: mat = [[0,0],[0,1]]
Output: 1
👨💻 Алгоритм:
1⃣Инициализируйте указатели на текущую строку и столбец, начиная с верхнего правого угла матрицы.
2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:
Если текущий элемент равен 0, сдвигайте указатель строки вниз.
Если текущий элемент равен 1, сдвигайте указатель столбца влево.
3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.
😎 Решение:
class Solution {
func leftMostColumnWithOne(_ binaryMatrix: BinaryMatrix) -> Int {
let dimensions = binaryMatrix.dimensions()
let rows = dimensions[0]
let cols = dimensions[1]
var currentRow = 0
var currentCol = cols - 1
while currentRow < rows && currentCol >= 0 {
if binaryMatrix.get(currentRow, currentCol) == 0 {
currentRow += 1
} else {
currentCol -= 1
}
}
return (currentCol == cols - 1) ? -1 : currentCol + 1
}
}Ставь 👍 и забирай 📚 Базу знаний