Поиск по первому появлению в матрице по времени требует сложности

Question

Мне нужно написать код psuedo для алгоритма, который получает в качестве входных данных матрицу (nxm) и выводит индекс строки первого появления 0

Я должен описать два алгоритма, которые выполняет один из них в O (mlogn), а второй выполняет в O (m + n)

Специальный атрибут матрицы:
Матрица состоит только из 0 и 1.
Как только введено нулевое значение, все столбцы ниже этой ячейки также должны быть равны нулю.

Пример правильного ввода:

1 1 1 1 1 1
1 0 1 1 1 1  
1 0 0 1 0 1
1 0 0 0 0 1
0 0 0 0 0 0

Вывод должен быть: 1

Редактировать: мне удалось придумать алгоритм с O (mlogn).

Answer 1

1-й алгоритм O (m * log (n))

Внутри столбца значения отсортированы в порядке убывания. Это означает, что вы можете найти первые 0 в O(log(n)), используя двоичный поиск внутри столбца.

Есть m столбцов для поиска. Это приводит к O(m*log(n)) для поиска во всех столбцах их первого 0. Нахождение первого 0 среди этих m результатов составляет O(m), в котором преобладает O(m*log(n)) предыдущего поиска.

2-й алгоритм O (m + n)

Второй алгоритм начинается с ячейки в (n,m). Для каждого столбца, начиная с последнего, мы go поднимаемся, пока находимся в ячейке с 0. Когда мы нажимаем 1, мы переходим к предыдущему столбцу.

i <- n
j <- m
r <- (-1, -1)
while (j >= 0):
  if M(i,j) == 1:
    j <- j-1
    continue
  while (i >= 0 && M(i,j) == 0)
    r <- (i,j)
    i <- i-1

В конце результат находится в r или не было никакого результата и r = (-1,-1)

Answer 2

Изменить: Этот ответ был для старого вопроса, который не включал Специальный атрибут матрицы

---

Я не думаю, что можно придумать алгоритм, который работает лучше, чем O (mn) в худшем случае.

Вот наивное решение, которое проверяет каждый элемент матрицы.

def solve(mat, n, m):
   for i in range(1, n):
      for j in range(i, m):
         if mat[i][j] == 0:
            return i

   return -1

В худшем случае (например, когда есть во входной матрице нет нулей):

Внешний для l oop будет выполняться n раз, а для каждой итерации внутренний для l oop будет выполняться m раз.

Таким образом, общая сложность времени будет O (m * n)