Напишите функцию, которая принимает отсортированную матрицу уникальных целых чисел и целевое целое число, и возвращает массив индексов строки и столбцов целого целого числа. Вернуть [-1, -1] Если целое число целевого показателя не найдено. Матрица может иметь другую высоту и ширину.
matrix = [
[1, 4, 7, 12, 15, 1000],
[2, 5, 19, 31, 32, 1001],
[3, 8, 24, 33, 35, 1002],
[40, 41, 42, 44, 45, 1003],
[99, 100, 103, 106, 128, 1004],
]
target = 44
[3, 3]
def search_in_sorted_matrix(matrix, target):
ptr_row = 0
ptr_col = len(matrix[0]) - 1
while ptr_row > -1 and ptr_col > -1 and ptr_row < len(matrix) and ptr_col < len(matrix[0]):
if target > matrix[ptr_row][ptr_col]:
ptr_row += 1
elif target < matrix[ptr_row][ptr_col]:
ptr_col -= 1
else:
return [ptr_row, ptr_col]
return [-1, -1]
- Попробуйте запустить поиск из верхнего правого уголка матрицы, затем надлежащим образом увеличить или уменьшить индексы строки или столбца.
- AlgoExpert для оператора проблемы
- Xkcd для изображения обложки
Оригинал: “https://dev.to/anzhari/today-i-learned-searching-inside-a-sorted-matrix-nge”