Постановка задачи. Найдите количество отрицательных целых чисел в матрице, отсортированной по строкам/столбцам.
Решение:
Понимание проблемы
Рассмотрим матрицу M с 3 строками и 4 столбцами как
Отрицательные целые числа в строке 1 равны 3
Отрицательные целые числа в строке 2 равны 1
Отрицательные целые числа в строке 3 равны 0
Таким образом, общее количество отрицательных целых чисел равно 3 + 1 + 0 = 4.
Наивное решение:
Начните с первого элемента M[0][0] и продолжайте считать, пока не встретите положительное число.
Повторите это для всех строк, а затем добавьте количество отрицательных чисел, найденных в каждой строке.
Сложность в худшем случае: если все элементы матрицы отрицательны, нам придется пройти всю матрицу. Таким образом, сложность будет O(nm), где n — количество строк, а m — количество столбцов.
Оптимальное решение:
Начните с последнего элемента строки M[0][m-1]
Пройдите влево и найдите отрицательное число, все числа слева от этого числа будут отрицательными, поэтому общее количество отрицательных элементов, присутствующих в этой строке, будет (индекс первого отрицательного элемента, встречающегося справа + 1)
Поскольку матрица отсортирована по столбцам, пройдите вниз по отрицательному числу, найденному в предыдущей строке, и повторите процесс шага 1.
Сложность этого подхода будет O(n+m)
Алгоритм:
M — матрица, n — количество строк, m — количество столбцов.
