Блог

Это вопрос, заданный на одном собеседовании. Я хотел бы знать наилучший оптимальный алгоритм для получения желаемых результатов. Вопрос в следующем: учитывая, что у вас есть матрица (n x m) с некоторыми числами в ней. Теперь вам нужно подсчитать количество матриц размера> = (2 x 2), которые будут иметь следующие два условия :

• В нем должно быть не менее двух единиц ;
• Два угловых элемента матрицы равны.

Я знаю алгоритм перебора всех элементов матрицы 2 x 2 и больше; затем подсчитываю количество единиц и проверяю 6 возможных условий угловых элементов, при которых любые два из них равны. Я хочу знать, как справиться с этими проблемами или каким-либо источником, поскольку я ничего не смог найти в «GeeksforGeeks» или в самом StackOverflow, наиболее оптимизированным способом.

Это подсказка к оптимизированному способу.

Сначала постройте (n, m) матрицу, которая подсчитывает количество 1 в (1-i, 1-j) подматрице: n m операций, n m памяти

Теперь для каждого элемента матрицы выполните поиск всех элементов после из ниже, которые равны

• если в той же строке вы можете использовать любую строку ниже, чтобы получить матрицу с 2 углами, равными
• если в том же столбце вы можете использовать любой столбец после, чтобы получить матрицу с 2 углами, равными
• если ни в одной строке, ни в одном столбце у вас нет ровно одной матрицы с 2 углами, равными
• разница элементов крайних углов эквивалентной матрицы от предварительно вычисленной — это количество единиц в подматрице
• как только в одной подматрице будет более 2 единиц, все подматрицы, включая ее, также будут иметь: вы можете использовать его для короткого замыкания полного анализа

Выше приведены только грубые края, и еще предстоит некоторая работа по разработке алгоритма, но это должно быть немного лучше, чем грубая сила для достаточно больших матриц…