Найдите строки с максимальным числом 0 в 2-й матрице

Question

Задача

По заданной матрице 2D 0/1 найдите строки с максимальным числом 0 с.

Пример

11111000
11111110
11100000
11000000
11110000

Выход

11000000

---

Моя идея

Если каждая строка 0 является непрерывной, мы можем сканировать с двух концов для каждой строки.Здравый смысл говорит, что сканировать с помощью O(n^2).

Есть ли какие-нибудь решения O(n)?

Answer 1

если каждая строка похожа на 1 .... 10 ... 0, вы можете выполнить двоичный поиск первого нуля в каждой строке.

Это будет O (n * lg (n))

для произвольной матрицы вы должны проверить каждую ячейку, поэтому она должна быть O (n ^ 2).

Answer 2

Вы можете сделать это в O(N) следующим образом:

Начните с A[i][j] с i=0 and j=No_of_columns-1.

           0, keep moving to the left by doing j--
A[i][j] = 
           1, move down to the next row by doing i++

Когда вы дойдете до последней строки или последнего столбца, ответом будет значение j.

Псевдокод:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1   
Let max1Row = 0

while ( i<R && j>=0 )
   if ( matrix[i][j] == 0 )
      j--
      max1Row = i
   else
      i++
end-while


print "Max 0's = j"
print "Row number with max 0's = max1Row"

Answer 3

Как говорит @amit:

сканирование матрицы считается O (n).Стандартное обозначение Big O обозначает связь между временем выполнения и размером ввода.Поскольку ваш ввод имеет размер # row * # cols, вы должны рассматривать это число как n, а не как # row.

Следовательно, это как O(n), как вы можете получить.:)

std::vector<std::string> matrix;
std::vector<std::string>::iterator max = matrix.begin();

for(std::vector<std::string>::iterator i = matrix.begin(); i != matrix.end(); ++i)
{
    if(count_zeros(*i) > count_zeros(*max))
        max = i;
}

count_zeros() должно выглядеть примерно так:

size_t count_zeros(std::string s)
{
    size_t count = 0;

    for(std::string::iterator i = s.begin(); i != s.end(); ++i)
        if(*i == '0')
            ++count;

    return i;
}

---

Если все 0 в каждой строке гарантированычтобы быть справа, вы можете сделать это в O(sqrt(n)).

1. Установить курсор на (len, 0)
2. Если значение слева от курсора равно 0,переместите курсор влево.В противном случае переместите его вниз.
3. Если достигнут нижний ряд, завершите.Иначе, перейдите к шагу 2.

std::vector<std::string> matrix;
std::vector<std::string>::iterator y = matrix.begin();

for(std::string::reverse_iterator x = (*y).rbegin(); x < matrix.rend(); )
{
    if(*x != '0')
    {
        x -= (*y).rbegin();
        ++(*y);
        x += (*y).rbegin();
        continue;
    }

    ++x;
}

Answer 4

Здесь быстрое решение только с одной строкой if или для каждой строки (не для каждого элемента): поскольку ваша матрица содержит только нули и единицы, сложите элементы каждой строки и затем верните индекс / индексы минимума / минимума.

PS: их добавление происходит очень быстро при использовании ассемблера inc или ++. Переменная в C ++

Редактировать: Здесь другая идея.Если вам действительно нужны матрицы 0/1, которые не превышают, скажем, 64 столбца, вы можете реализовать их в виде битовых матриц, используя обычные беззнаковые 64 целых числа.Устанавливая и удаляя соответствующий бит, вы можете определить запись (0 или 1).Эффект: проверка o (n) (дайте мне знать, если я ошибаюсь) следующим образом, где intXX - rowXX.Первая идея состоит в том, чтобы извлечь различные биты с помощью XOR

SET tmpA to int01
FOR I = 1 to n-1
  XOR intI with intI+1, store result in tmpX
  AND tmpX with intI, store result in tmpM
  AND tmpX with intI+1, store result in tmpN
  if (tmpN < tmpM)
    SET tmpA to intI+1
ENDFOR

. Теперь tmpA должен содержать (последнюю) строку с наименьшим количеством нулей.

Cheers, G.

Answer 5

При заданном наборе выборок (все начинаются с 111 и заканчиваются на 000 без смешивания 1 и 0), набор можно просто найти за один проход с проверкой A & (A xor B) для проверки, если есть больше или меньше нуля, чем предыдущая строка - это цикл O (n) ....