Dada una array cuadrada arr[][] de tamaño N que consta de números enteros no negativos y un número entero K , la tarea es encontrar el valor medio máximo de los elementos de una subarray cuadrada de tamaño K .
Ejemplos:
Entrada: arr[][] = {{1, 5, 12}, {6, 7, 11}, {8, 9, 10}}, N = 3, K = 2
Salida: 9
Explicación:
La mediana de todos subcuadrado de tamaño 2*2 son:
- El subcuadrado {{1, 5}, {6, 7}} tiene la mediana igual a 5.
- El subcuadrado {{5, 12}, {7, 11}} tiene la mediana igual a 7.
- El subcuadrado {{6, 7}, {8, 9}} tiene la mediana igual a 7.
- El subcuadrado {{7, 11}, {9, 10}} tiene la mediana igual a 9.
Por lo tanto, el valor mediano máximo posible entre todas las arrays cuadradas posibles es igual a 9.
Entrada: arr[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 10, 11}, {12, 13, 14, 13}}, N = 4, K = 2
Salida: 11
Enfoque ingenuo: el enfoque más simple para resolver el problema anterior es iterar sobre cada subarray de tamaño K*K y luego encontrar la mediana máxima entre todas las subarray formadas.
Complejidad de Tiempo: O(N 2 * K 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema anterior se puede optimizar en función de las siguientes observaciones:
- Si M es la mediana de una subarray cuadrada, entonces el recuento de números menores o iguales que M en esa subarray debe ser menor que (K 2 +1)/2 .
- La idea es utilizar la búsqueda binaria para encontrar el valor medio dado como:
- Si el recuento de números menores que M en cualquier subarray de tamaño K×K es menor que (K 2 +1)/2, entonces incremente el límite izquierdo.
- De lo contrario, disminuya el límite derecho.
- La idea es usar el prefijo suma de la array para contar los elementos menores que un valor particular en tiempo constante en una subarray cuadrada.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos un valor bajo como 0 y un valor alto como INT_MAX que representan el rango del espacio de búsqueda.
- Iterar hasta que bajo sea menor que alto y realizar los siguientes pasos:
- Encuentre el valor medio del rango [bajo, alto] y guárdelo en una variable, digamos mid .
- Inicialice el vector de vectores , diga Pre para almacenar el recuento de elementos menores o iguales a mid en una subarray de prefijo.
- Iterar sobre cada elemento de la array arr[][] usando las variables i y j y actualizar el valor de Pre[i + 1][j + 1] como Pre[i + 1][j] + Pre[i][j + 1] – Pre[i][j] y luego incrementa Pre[i + 1][j + 1] en 1 si arr[i][j] es menor o igual que mid .
- Inicialice una variable, diga marcar como falso para almacenar si el valor de mid es posible o no como la mediana.
- Iterar sobre cada valor posible del par (i, j) de [K, N]*[K, N] y luego realizar los siguientes pasos:
- Encuentre el recuento de elementos menores o iguales a la mitad de la subarray cuadrada con el vértice superior izquierdo como (i – K, j – K) y el vértice inferior derecho como (i, j) y luego guárdelo en una variable, digamos X como Pre[i][j] – Pre[i – K][j] – Pre[i][j – K]+ Pre[i – K][j – K] .
- Si X es menor que (K 2 +1)/2 , marque la bandera como verdadera y salga del bucle .
- Si la bandera es verdadera , actualice el valor de bajo como (medio + 1) . De lo contrario, actualice el valor de alto como medio .
- Después de completar los pasos anteriores, imprima el valor de low como la mediana máxima obtenida entre todas las posibles subarray cuadrada de tamaño K*K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to determine if a given
// value can be median
bool isMaximumMedian(vector<vector<int> >& arr,
int N, int K, int mid)
{
// Stores the prefix sum array
vector<vector<int> > Pre(
N + 5, vector<int>(N + 5, 0));
// Traverse the matrix arr[][]
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
// Update Pre[i+1][j+1]
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
// If arr[i][j] is less
// than or equal to mid
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
// Stores the count of elements
// should be less than mid
int required = (K * K + 1) / 2;
// Stores if the median mid
// can be possible or not
bool flag = 0;
// Iterate over the range [K, N]
for (int i = K; i <= N; ++i) {
// Iterate over the range [K, N]
for (int j = K; j <= N; ++j) {
// Stores count of elements less
// than or equal to the value
// mid in submatrix with bottom
// right vertices at (i, j)
int X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
// If X is less than or
// equal to required
if (X < required)
flag = 1;
}
}
// Return flag
return flag;
}
// Function to find the maximum median
// of a subsquare of the given size
int maximumMedian(vector<vector<int> >& arr,
int N, int K)
{
// Stores the range of the
// search space
int low = 0, high = 1e9;
// Iterate until low is less
// than high
while (low < high) {
// Stores the mid value of
// the range [low, high]
int mid = low + (high - low) / 2;
// If the current median can
// be possible
if (isMaximumMedian(arr, N, K, mid)) {
// Update the value of low
low = mid + 1;
}
else {
// Update the value of high
high = mid;
}
}
// Return value stored in low as
// answer
return low;
}
// Driver Code
int main()
{
vector<vector<int> > arr
= { { 1, 5, 12 }, { 6, 7, 11 }, { 8, 9, 10 } };
int N = arr.size();
int K = 2;
cout << maximumMedian(arr, N, K);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to determine if a given
// value can be median
static boolean isMaximumMedian(int arr[][] , int N, int K, int mid)
{
// Stores the prefix sum array
int [][]Pre = new int [N+5][N+5];
// Traverse the matrix arr[][]
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
// Update Pre[i+1][j+1]
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
// If arr[i][j] is less
// than or equal to mid
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
// Stores the count of elements
// should be less than mid
int required = (K * K + 1) / 2;
// Stores if the median mid
// can be possible or not
boolean flag = false;
// Iterate over the range [K, N]
for (int i = K; i <= N; ++i) {
// Iterate over the range [K, N]
for (int j = K; j <= N; ++j) {
// Stores count of elements less
// than or equal to the value
// mid in submatrix with bottom
// right vertices at (i, j)
int X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
// If X is less than or
// equal to required
if (X < required)
flag = true;
}
}
// Return flag
return flag;
}
// Function to find the maximum median
// of a subsquare of the given size
static int maximumMedian(int arr[][], int N, int K)
{
// Stores the range of the
// search space
int low = 0, high = (int)1e9;
// Iterate until low is less
// than high
while (low < high) {
// Stores the mid value of
// the range [low, high]
int mid = low + (high - low) / 2;
// If the current median can
// be possible
if (isMaximumMedian(arr, N, K, mid)) {
// Update the value of low
low = mid + 1;
}
else {
// Update the value of high
high = mid;
}
}
// Return value stored in low as
// answer
return low;
}
// Driver Code
public static void main(String args[])
{
int [][] arr = { { 1, 5, 12 }, { 6, 7, 11 }, { 8, 9, 10 } };
int N = arr.length;
int K = 2;
System.out.print( maximumMedian(arr, N, K));
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach # Function to determine if a given # value can be median def isMaximumMedian(arr, N, K, mid): # Stores the prefix sum array Pre = [[0 for x in range(N + 5)] for y in range(N + 5)] # Traverse the matrix arr[][] for i in range(N): for j in range(N): # Update Pre[i+1][j+1] Pre[i + 1][j + 1] = (Pre[i + 1][j] + Pre[i][j + 1] - Pre[i][j]) # If arr[i][j] is less # than or equal to mid if (arr[i][j] <= mid): Pre[i + 1][j + 1] += 1 # Stores the count of elements # should be less than mid required = (K * K + 1) // 2 # Stores if the median mid # can be possible or not flag = 0 # Iterate over the range [K, N] for i in range(K, N + 1): # Iterate over the range [K, N] for j in range(K, N + 1): # Stores count of elements less # than or equal to the value # mid in submatrix with bottom # right vertices at (i, j) X = (Pre[i][j] - Pre[i - K][j] - Pre[i][j - K] + Pre[i - K][j - K]) # If X is less than or # equal to required if (X < required): flag = 1 # Return flag return flag # Function to find the maximum median # of a subsquare of the given size def maximumMedian(arr, N, K): # Stores the range of the # search space low = 0 high = 1000000009 # Iterate until low is less # than high while (low < high): # Stores the mid value of # the range [low, high] mid = low + (high - low) // 2 # If the current median can # be possible if (isMaximumMedian(arr, N, K, mid)): # Update the value of low low = mid + 1 else: # Update the value of high high = mid # Return value stored in low as # answer return low # Driver Code if __name__ == "__main__": arr = [ [ 1, 5, 12 ], [ 6, 7, 11 ], [ 8, 9, 10 ] ] N = len(arr) K = 2 print(maximumMedian(arr, N, K)) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
class GFG{
// Function to determine if a given
// value can be median
static bool isMaximumMedian(int[,] arr, int N,
int K, int mid)
{
// Stores the prefix sum array
int [,]Pre = new int[N + 5, N + 5];
// Traverse the matrix arr[][]
for(int i = 0; i < N; ++i)
{
for(int j = 0; j < N; ++j)
{
// Update Pre[i+1][j+1]
Pre[i + 1, j + 1] = Pre[i + 1, j] +
Pre[i, j + 1] -
Pre[i, j];
// If arr[i][j] is less
// than or equal to mid
if (arr[i, j] <= mid)
Pre[i + 1, j + 1]++;
}
}
// Stores the count of elements
// should be less than mid
int required = (K * K + 1) / 2;
// Stores if the median mid
// can be possible or not
bool flag = false;
// Iterate over the range [K, N]
for(int i = K; i <= N; ++i)
{
// Iterate over the range [K, N]
for(int j = K; j <= N; ++j)
{
// Stores count of elements less
// than or equal to the value
// mid in submatrix with bottom
// right vertices at (i, j)
int X = Pre[i, j] - Pre[i - K, j] -
Pre[i, j - K] + Pre[i - K, j - K];
// If X is less than or
// equal to required
if (X < required)
flag = true;
}
}
// Return flag
return flag;
}
// Function to find the maximum median
// of a subsquare of the given size
static int maximumMedian(int[,] arr, int N, int K)
{
// Stores the range of the
// search space
int low = 0, high = (int)1e9;
// Iterate until low is less
// than high
while (low < high)
{
// Stores the mid value of
// the range [low, high]
int mid = low + (high - low) / 2;
// If the current median can
// be possible
if (isMaximumMedian(arr, N, K, mid))
{
// Update the value of low
low = mid + 1;
}
else
{
// Update the value of high
high = mid;
}
}
// Return value stored in low as
// answer
return low;
}
// Driver code
public static void Main(string[] args)
{
int [,] arr = { { 1, 5, 12 },
{ 6, 7, 11 },
{ 8, 9, 10 } };
int N = arr.GetLength(0);
int K = 2;
Console.WriteLine(maximumMedian(arr, N, K));
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
// JavaScript Program for the above approach
// Function to determine if a given
// value can be median
function isMaximumMedian(arr, N, K, mid) {
// Stores the prefix sum array
let Pre = Array(N + 5).fill().map(() => Array(N + 5).fill(0));
// Traverse the matrix arr[][]
for (let i = 0; i < N; ++i) {
for (let j = 0; j < N; ++j) {
// Update Pre[i+1][j+1]
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
// If arr[i][j] is less
// than or equal to mid
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
// Stores the count of elements
// should be less than mid
let required = Math.floor((K * K + 1) / 2);
// Stores if the median mid
// can be possible or not
let flag = 0;
// Iterate over the range [K, N]
for (let i = K; i <= N; ++i) {
// Iterate over the range [K, N]
for (let j = K; j <= N; ++j) {
// Stores count of elements less
// than or equal to the value
// mid in submatrix with bottom
// right vertices at (i, j)
let X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
// If X is less than or
// equal to required
if (X < required)
flag = 1;
}
}
// Return flag
return flag;
}
// Function to find the maximum median
// of a subsquare of the given size
function maximumMedian(arr, N, K) {
// Stores the range of the
// search space
let low = 0, high = 1e9;
// Iterate until low is less
// than high
while (low < high) {
// Stores the mid value of
// the range [low, high]
let mid = low + Math.floor((high - low) / 2);
// If the current median can
// be possible
if (isMaximumMedian(arr, N, K, mid)) {
// Update the value of low
low = mid + 1;
}
else {
// Update the value of high
high = mid;
}
}
// Return value stored in low as
// answer
return low;
}
// Driver Code
let arr
= [[1, 5, 12], [6, 7, 11], [8, 9, 10]];
let N = arr.length;
let K = 2;
document.write(maximumMedian(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
9
Complejidad de tiempo: O(N 2 * log(10 9 ))
Espacio auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA