Максимизируйте медиану подсетки KxK в сетке NxN

Дана квадратная матрица arr[][] размера N , состоящая из неотрицательных целых чисел и целого числа K , задача состоит в том, чтобы найти максимальное медианное значение элементов квадратной подматрицы размера K .

Примеры:

Input: arr[][] = {{1, 5, 12}, {6, 7, 11}, {8, 9, 10}}, N = 3, K = 2
Output: 9
Explanation: 
The median of all subsquare of size 2*2 are:

1. The subsquare {{1, 5}, {6, 7}} has the median equal to 5.
2. The subsquare {{5, 12}, {7, 11}} has the median equal to 7.
3. The subsquare {{6, 7}, {8, 9}} has the median equal to 7.
4. The subsquare {{7, 11}, {9, 10}} has the median equal to 9.

Therefore, the maximum possible median value among all possible square matrix is equal to 9.

Input: arr[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 10, 11}, {12, 13, 14, 13}}, N = 4, K = 2
Output: 11

Наивный подход: самый простой подход к решению данной выше проблемы состоит в том, чтобы перебрать каждую подматрицу размера K * K , а затем найти максимальную медиану среди всех сформированных подматриц.

Временная сложность: O(N ² * K ² )
Вспомогательное пространство: O(1)

Эффективный подход . Вышеупомянутая задача может быть оптимизирована на основе следующих наблюдений:

• Если M является медианой квадратной подматрицы, то количество чисел, меньших или равных M в этой подматрице, должно быть меньше (K ² +1)/2 .
• Идея состоит в том, чтобы использовать бинарный поиск, чтобы найти заданное медианное значение как:
  • Если количество чисел меньше M в любой подматрице размера K×K меньше (K ² +1)/2, то увеличивается левая граница.
  • В противном случае уменьшите правую границу.
• Идея состоит в том, чтобы использовать сумму префикса для матрицы для подсчета элементов, меньших определенного значения, за постоянное время в квадратной подматрице.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте две переменные, скажем, младшее значение равно 0 , а высокое значение равно INT_MAX , представляющее диапазон пространства поиска.
• Повторяйте до тех пор, пока низкий уровень не станет меньше высокого , и выполните следующие шаги:
  • Найдите среднее значение диапазона [low, high] и сохраните его в переменной, например, mid .
  • Инициализируйте вектор векторов, скажем Pre , чтобы сохранить количество элементов, меньших или равных середине, в подматрице префикса.
  • Перебрать каждый элемент матрицы arr[][] с использованием переменных i и j и обновить значение Pre[i + 1][j + 1] как Pre[i + 1][j] + Pre[i][j + 1] – Pre[i][j] и затем увеличить Pre[i + 1][j + 1] на 1 , если arr[i][j] меньше или равно mid .
  • Инициализируйте переменную, скажем, отметьте как false , чтобы сохранить, возможно ли значение середины или нет в качестве медианы.
  • Перебрать все возможные значения пару (i, j) из [K, N] * [K, N], а затем выполните следующие шаги:
    • Найдите количество элементов, меньшее или равное середине в квадратной подматрице с верхней левой вершиной как (i – K, j – K) и нижней правой вершиной как (i, j), а затем сохраните его в переменной, скажем, X как Pre[i][j] – Pre[i – K][j] – Pre[i][j – K]+ Pre[i – K][j – K] .
    • Если X меньше (K ² +1)/2 , то пометить флаг как истинный и выйти из цикла.
  • Если флаг равен true , обновите значение low как (mid + 1) . В противном случае обновите значение high как mid .
• После выполнения вышеуказанных шагов выведите значение low как максимальную медиану, полученную среди всех возможных квадратных подматриц размера K*K .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² * log(10 ⁹ ))
Вспомогательное пространство: O(N ² )