Учитывая булеву матрицу, отсортированный по ряду. Вернуть строку с максимальным числом 1

Я столкнулся с проблемой Матриц, но пытался найти оптимальное решение. Постановка проблемы - это сама тема вопроса. Далее смотрите ниже

Example
Input matrix

  0 1 1 1
  0 0 1 1
  1 1 1 1  // this row has maximum 1s
  0 0 0 0

Output: 2

Мое решение: теперь, так как строки отсортированы, я подумал о выполнении бинарного поиска в каждой строке с первым появлением 1, а затем счет 1 будет total number of columns minus index of 1st 1,

Это сделает это в O(m*logn), но мне было любопытно узнать логику, если это можно сделать за линейное время.

Спасибо!

Источник

2 ответа

Решение

Начать курсор в правом верхнем углу. В каждом ряду шагайте влево, пока не достигнете последней 1 в ряду. Тогда уходи. Если вы опускаетесь и курсор указывает на 0, снова опускайтесь. Никогда не идите прямо. Вы ищете ряд, который имеет 1 крайний слева, поэтому вам не нужно смотреть вправо. Время выполнения равно O(n+m), так как вы проходите каждую строку, отступаете m раз и делаете в общей сложности не более n шагов. Вот некоторый псевдокод, предполагая, что матрица представляет собой список списков:

bestrow = 0
leftmost = matrix.width

for i = matrix.height to 0:
    row = matrix[i]
    while row[leftmost - 1] == 1:
        leftmost--
        bestrow = i

return bestrow

Если вы переводите код буквально, у вас могут возникнуть проблемы с матрицей всех 0 или если в какой-то строке есть все 1. С ними довольно легко иметь дело, и смысл псевдокода - просто передать общий алгоритм.

Источник

Решение этой проблемы зависит от количества элементов в каждой строке и количества столбцов. Вот подход.

Шаг 1: Просто выполните двоичную операцию && для всех элементов в каждом столбце, пока не получите значение true, что означает, что мы нашли столбец, в котором есть хотя бы один столбец. Это займет максимум n шагов, где n - количество столбцов.

Шаг 2: Теперь выполните поиск по одному сверху вниз в этом столбце, чтобы получить строку с максимальным количеством единиц. Это занимает не более m шагов. Где m - количество строк. Таким образом, в целом требуется O(m+n) шагов.

Это также поможет вам найти несколько строк, если таковые имеются с тем же свойством

Источник
Другие вопросы по тегам