Dada una array arr[][] y un entero K , la tarea es encontrar el elemento más pequeño de todas las subarrays cuadradas posibles de tamaño K de la array dada.
Ejemplos:
Entrada: K = 2, arr[][] ={ {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }
Salida:
1 2
4 5
Explicación:
Los elementos más pequeños de todos los posibles subarrays cuadradas de tamaño 2 son las siguientes:
{ {1, 2}, {4, 5} } -> 1
{ {2, 3}, {5, 6} } -> 2
{ {4, 5}, {7 , 8} } -> 4
{ {5, 6}, {8, 9} } -> 5Entrada: K = 3,
arr[][] = { {-1, 5, 4, 1, -3},
{4, 3, 1, 1, 6},
{2, -2, 5, 3, 1 },
{8, 5, 1, 9, -4},
{12, 3, 5, 8, 1} }
Salida:
-2 -2 -3
-2 -2 -4
-2 -2 -4
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subarrays cuadradas posibles de tamaño K a partir de la array dada e imprimir el elemento más pequeño de cada una de esas subarrays.
Complejidad de Tiempo: O(N * M * K 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Recorra cada fila de la array y para cada arr[i][j], actualice en el lugar el elemento más pequeño presente entre los índices arr[i][j] a arr[i][j + K – 1] ( 0 < = j < METRO – K + 1) .
- De manera similar, recorra cada columna de la array y para cada arr[i][j], actualice en el lugar el elemento más pequeño presente entre los índices arr[i][j] a arr[i+K-1][j] ( 0 <= yo < norte – K + 1) .
- Después de realizar las operaciones anteriores, la subarray superior izquierda de tamaño (N – K + 1)*(M – K + 1) de la array arr[][] consta de todos los elementos más pequeños de todas las sub – K x K arrays de la array dada.
- Por lo tanto, imprima la subarray de tamaño (N – K + 1)*(M – K + 1) como la salida requerida.
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 returns a smallest
// elements of all KxK submatrices
// of a given NxM matrix
vector<vector<int> > matrixMinimum(
vector<vector<int> > nums, int K)
{
// Stores the dimensions
// of the given matrix
int N = nums.size();
int M = nums[0].size();
// Stores the required
// smallest elements
vector<vector<int> > res(N - K + 1,
vector<int>(M - K + 1));
// Update the smallest elements row-wise
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M - K + 1; j++)
{
int mini = INT_MAX;
for (int k = j; k < j + K; k++)
{
mini = min(mini, nums[i][k]);
}
nums[i][j] = mini;
}
}
// Update the minimum column-wise
for (int j = 0; j < M; j++)
{
for (int i = 0; i < N - K + 1; i++)
{
int mini = INT_MAX;
for (int k = i; k < i + K; k++)
{
mini = min(mini, nums[k][j]);
}
nums[i][j] = mini;
}
}
// Store the final submatrix with
// required minimum values
for (int i = 0; i < N - K + 1; i++)
for (int j = 0; j < M - K + 1; j++)
res[i][j] = nums[i][j];
// Return the resultant matrix
return res;
}
void smallestinKsubmatrices(vector<vector<int> > arr,
int K)
{
// Function Call
vector<vector<int> > res = matrixMinimum(arr, K);
// Print resultant matrix with the
// minimum values of KxK sub-matrix
for (int i = 0; i < res.size(); i++)
{
for (int j = 0; j < res[0].size(); j++)
{
cout << res[i][j] << " ";
}
cout << endl;
}
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > arr = {{-1, 5, 4, 1, -3},
{4, 3, 1, 1, 6},
{2, -2, 5, 3, 1},
{8, 5, 1, 9, -4},
{12, 3, 5, 8, 1}};
// Given K
int K = 3;
smallestinKsubmatrices(arr, K);
}
// This code is contributed by Chitranayal
Java
// Java Program for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to returns a smallest
// elements of all KxK submatrices
// of a given NxM matrix
public static int[][] matrixMinimum(
int[][] nums, int K)
{
// Stores the dimensions
// of the given matrix
int N = nums.length;
int M = nums[0].length;
// Stores the required
// smallest elements
int[][] res
= new int[N - K + 1][M - K + 1];
// Update the smallest elements row-wise
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - K + 1; j++) {
int min = Integer.MAX_VALUE;
for (int k = j; k < j + K; k++) {
min = Math.min(min, nums[i][k]);
}
nums[i][j] = min;
}
}
// Update the minimum column-wise
for (int j = 0; j < M; j++) {
for (int i = 0; i < N - K + 1; i++) {
int min = Integer.MAX_VALUE;
for (int k = i; k < i + K; k++) {
min = Math.min(min, nums[k][j]);
}
nums[i][j] = min;
}
}
// Store the final submatrix with
// required minimum values
for (int i = 0; i < N - K + 1; i++)
for (int j = 0; j < M - K + 1; j++)
res[i][j] = nums[i][j];
// Return the resultant matrix
return res;
}
public static void smallestinKsubmatrices(
int arr[][], int K)
{
// Function Call
int[][] res = matrixMinimum(arr, K);
// Print resultant matrix with the
// minimum values of KxK sub-matrix
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[0].length; j++) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int[][] arr = { { -1, 5, 4, 1, -3 },
{ 4, 3, 1, 1, 6 },
{ 2, -2, 5, 3, 1 },
{ 8, 5, 1, 9, -4 },
{ 12, 3, 5, 8, 1 } };
// Given K
int K = 3;
smallestinKsubmatrices(arr, K);
}
}
Python3
# Python3 program for the above approach import sys # Function to returns a smallest # elements of all KxK submatrices # of a given NxM matrix def matrixMinimum(nums, K): # Stores the dimensions # of the given matrix N = len(nums) M = len(nums[0]) # Stores the required # smallest elements res = [[0 for x in range(M - K + 1)] for y in range(N - K + 1)] # Update the smallest elements row-wise for i in range(N): for j in range(M - K + 1): mn = sys.maxsize for k in range(j, j + K): mn = min(mn, nums[i][k]) nums[i][j] = mn # Update the minimum column-wise for j in range(M): for i in range(N - K + 1): mn = sys.maxsize for k in range(i, i + K): mn = min(mn, nums[k][j]) nums[i][j] = mn # Store the final submatrix with # required minimum values for i in range(N - K + 1): for j in range(M - K + 1): res[i][j] = nums[i][j] # Return the resultant matrix return res def smallestinKsubmatrices(arr, K): # Function call res = matrixMinimum(arr, K) # Print resultant matrix with the # minimum values of KxK sub-matrix for i in range(len(res)): for j in range(len(res[0])): print(res[i][j], end = " ") print() # Driver Code # Given matrix arr = [ [ -1, 5, 4, 1, -3 ], [ 4, 3, 1, 1, 6 ], [ 2, -2, 5, 3, 1 ], [ 8, 5, 1, 9, -4 ], [ 12, 3, 5, 8, 1 ] ] # Given K K = 3 # Function call smallestinKsubmatrices(arr, K) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to returns a smallest
// elements of all KxK submatrices
// of a given NxM matrix
public static int[,] matrixMinimum(int[,] nums,
int K)
{
// Stores the dimensions
// of the given matrix
int N = nums.GetLength(0);
int M = nums.GetLength(1);
// Stores the required
// smallest elements
int[,] res = new int[N - K + 1,
M - K + 1];
// Update the smallest elements row-wise
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M - K + 1; j++)
{
int min = int.MaxValue;
for(int k = j; k < j + K; k++)
{
min = Math.Min(min, nums[i, k]);
}
nums[i, j] = min;
}
}
// Update the minimum column-wise
for(int j = 0; j < M; j++)
{
for(int i = 0; i < N - K + 1; i++)
{
int min = int.MaxValue;
for(int k = i; k < i + K; k++)
{
min = Math.Min(min, nums[k, j]);
}
nums[i, j] = min;
}
}
// Store the readonly submatrix with
// required minimum values
for(int i = 0; i < N - K + 1; i++)
for(int j = 0; j < M - K + 1; j++)
res[i, j] = nums[i, j];
// Return the resultant matrix
return res;
}
public static void smallestinKsubmatrices(int [,]arr,
int K)
{
// Function call
int[,] res = matrixMinimum(arr, K);
// Print resultant matrix with the
// minimum values of KxK sub-matrix
for(int i = 0; i < res.GetLength(0); i++)
{
for(int j = 0; j < res.GetLength(1); j++)
{
Console.Write(res[i, j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int[,] arr = { { -1, 5, 4, 1, -3 },
{ 4, 3, 1, 1, 6 },
{ 2, -2, 5, 3, 1 },
{ 8, 5, 1, 9, -4 },
{ 12, 3, 5, 8, 1 } };
// Given K
int K = 3;
smallestinKsubmatrices(arr, K);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program for the
// above approach
// Function to returns a smallest
// elements of all KxK submatrices
// of a given NxM matrix
function matrixMinimum(
nums, K)
{
// Stores the dimensions
// of the given matrix
let N = nums.length;
let M = nums[0].length;
// Stores the required
// smallest elements
let res
= new Array(N - K + 1);
for (var i = 0; i < res.length; i++) {
res[i] = new Array(2);
}
// Update the smallest elements row-wise
for (let i = 0; i < N; i++) {
for (let j = 0; j < M - K + 1; j++) {
let min = Number.MAX_VALUE;
for (let k = j; k < j + K; k++) {
min = Math.min(min, nums[i][k]);
}
nums[i][j] = min;
}
}
// Update the minimum column-wise
for (let j = 0; j < M; j++) {
for (let i = 0; i < N - K + 1; i++) {
let min = Number.MAX_VALUE;
for (let k = i; k < i + K; k++) {
min = Math.min(min, nums[k][j]);
}
nums[i][j] = min;
}
}
// Store the final submatrix with
// required minimum values
for (let i = 0; i < N - K + 1; i++)
for (let j = 0; j < M - K + 1; j++)
res[i][j] = nums[i][j];
// Return the resultant matrix
return res;
}
function smallestinKsubmatrices(arr, K)
{
// Function Call
let res = matrixMinimum(arr, K);
// Print resultant matrix with the
// minimum values of KxK sub-matrix
for (let i = 0; i < res.length; i++) {
for (let j = 0; j < res[0].length; j++) {
document.write(res[i][j] + " ");
}
document.write("<br/>");
}
}
// Driver Code
// Given matrix
let arr = [[ -1, 5, 4, 1, -3 ],
[ 4, 3, 1, 1, 6 ],
[ 2, -2, 5, 3, 1 ],
[ 8, 5, 1, 9, -4 ],
[ 12, 3, 5, 8, 1 ]];
// Given K
let K = 3;
smallestinKsubmatrices(arr, K);
</script>
Producción:
-2 -2 -3 -2 -2 -4 -2 -2 -4
Complejidad de tiempo: O( max(N, M) 3 )
Espacio auxiliar: O( (N-K+1)*(M-K+1) )