Dada una array arr[] que consta de N enteros, la tarea es crear una array brr[] de tamaño N donde brr[i] representa el recuento de subarreglos en los que arr[i] es el elemento más pequeño.
Ejemplos:
Entrada: arr[] = {3, 2, 4}
Salida: {1, 3, 1}
Explicación:
Para arr[0], solo hay un subarreglo en el que 3 es el más pequeño ({3}).
Para arr[1], hay tres subarreglos donde 2 es el más pequeño ({2}, {3, 2}, {2, 4}).
Para arr[2], solo hay un subarreglo en el que 4 es el más pequeño ({4}).Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: {5, 4, 3, 2, 1}
Enfoque Hashing : recorra la array para encontrar el elemento mínimo para todos los subarreglos posibles y almacene su conteo en un Map . Siga los pasos a continuación para resolver el problema:
- Cree un mapa para almacenar el recuento de subarreglos para cada elemento.
- Recorra todos los subarreglo posibles para encontrar el elemento mínimo en el subarreglo.
- Incremento de conteo de los elementos mínimos obtenidos en el Mapa .
- Finalmente, imprima las frecuencias obtenidas en el Mapa para cada elemento del arreglo.
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 calculate total number
// of sub-arrays for each element
// where that element is occurring
// as the minimum element
void minSubarray(int* arr, int N)
{
// Map for storing the number of
// sub-arrays for each element
unordered_map<int, int> m;
// Traverse over all possible subarrays
for (int i = 0; i < N; i++) {
int mini = INT_MAX;
for (int j = i; j < N; j++) {
// Minimum in each subarray
mini = min(mini, arr[j]);
m[mini]++;
}
}
// Print the result
for (int i = 0; i < N; i++) {
cout << m[arr[i]] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1, 4 };
int N = sizeof(arr) / sizeof(int);
// Function Call
minSubarray(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to calculate total
// number of sub-arrays for each
// element where that element is
// occurring as the minimum element
static void minSubarray(int []arr,
int N)
{
// Map for storing the number of
// sub-arrays for each element
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse over all possible
// subarrays
for (int i = 0; i < N; i++)
{
int mini = Integer.MAX_VALUE;
for (int j = i; j < N; j++)
{
// Minimum in each subarray
mini = Math.min(mini, arr[j]);
if(mp.containsKey(mini))
{
mp.put(mini, mp.get(mini) + 1);
}
else
{
mp.put(mini, 1);
}
}
}
// Print the result
for (int i = 0; i < N; i++)
{
System.out.print(mp.get(arr[i]) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {3, 2, 1, 4};
int N = arr.length;
// Function Call
minSubarray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for
# the above approach
# Function to calculate total
# number of sub-arrays for
# each element where that
# element is occurring as the
# minimum element
def minSubarray(arr, N):
# Map for storing the
# number of sub-arrays
# for each element
m = {}
# Traverse over all
# possible subarrays
for i in range(N):
mini = 10 ** 9
for j in range(i, N):
# Minimum in each subarray
mini = min(mini, arr[j])
m[mini] = m.get(mini, 0) + 1
# Print result
for i in arr:
print(m[i], end = " ")
# Driver Code
if __name__ == '__main__':
arr = [3, 2, 1, 4]
N = len(arr)
# Function Call
minSubarray(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate total
// number of sub-arrays for each
// element where that element is
// occurring as the minimum element
static void minSubarray(int []arr,
int N)
{
// Map for storing the number of
// sub-arrays for each element
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse over all possible
// subarrays
for(int i = 0; i < N; i++)
{
int mini = int.MaxValue;
for(int j = i; j < N; j++)
{
// Minimum in each subarray
mini = Math.Min(mini, arr[j]);
if (mp.ContainsKey(mini))
{
mp[mini] = mp[mini] + 1;
}
else
{
mp.Add(mini, 1);
}
}
}
// Print the result
for(int i = 0; i < N; i++)
{
Console.Write(mp[arr[i]] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1, 4 };
int N = arr.Length;
// Function Call
minSubarray(arr, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate total number
// of sub-arrays for each element
// where that element is occurring
// as the minimum element
function minSubarray(arr, N)
{
// Map for storing the number of
// sub-arrays for each element
var m = new Map();
// Traverse over all possible subarrays
for (var i = 0; i < N; i++) {
var mini = 1000000000;
for (var j = i; j < N; j++) {
// Minimum in each subarray
mini = Math.min(mini, arr[j]);
if(m.has(mini))
m.set(mini, m.get(mini)+1)
else
m.set(mini, 1)
}
}
// Print the result
for (var i = 0; i < N; i++) {
document.write( m.get(arr[i]) + " ");
}
}
// Driver Code
var arr = [3, 2, 1, 4];
var N = arr.length;
// Function Call
minSubarray(arr, N);
</script>
Producción
1 2 6 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este enfoque se basa en el concepto del elemento mayor siguiente y el elemento mayor anterior . Siga los pasos a continuación para resolver el problema:
- Para encontrar la ocurrencia del elemento como mínimo, primero encuentre x e y , donde x es la longitud de los números estrictamente más grandes a la izquierda de arr[i] e y es la longitud de los números más grandes a la derecha de arr[ yo] .
- Por lo tanto, x * y es el número total de subarreglos en los que arr[i] es un mínimo.
- Para encontrar x e y use stack con el concepto del siguiente elemento mayor y el elemento mayor anterior .
- Para el siguiente elemento mayor , cree una pila de pares y empuje el primer elemento de la array y un contador para contar los subarreglos como un par en la pila.
- Recorra la array y elija el elemento de la array uno por uno:
- Si el elemento de array actual es mayor que el elemento superior de la pila , entonces para el elemento superior de la pila , el elemento actual es el siguiente elemento mayor . Entonces, extraiga el elemento superior de la pila e incremente el contador por el valor del contador en la parte superior de la pila , y luego el siguiente elemento superior de la pila se compara con el elemento de array actual y así sucesivamente.
- De lo contrario, inserte el elemento de array actual con el contador en la pila e inserte el contador en la array de resultados.
- Repita los pasos 4, 5 para el elemento mayor anterior.
- Finalmente, imprime el resultado.
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 count subarrays
// for each element where it is
// the minimum
void minSubarray(int* arr, int N)
{
int result[N];
stack<pair<int, int> > l, r;
// For the length of strictly larger
// numbers on the left of A[i]
for (int i = 0; i < N; i++) {
int count = 1;
while (!l.empty()
&& l.top().first > arr[i]) {
count += l.top().second;
l.pop();
}
l.push({ arr[i], count });
// Storing x in result[i]
result[i] = count;
}
// For the length of strictly larger
// numbers on the right of A[i]
for (int i = N - 1; i >= 0; i--) {
int count = 1;
while (!r.empty()
&& r.top().first >= arr[i]) {
count += r.top().second;
r.pop();
}
r.push({ arr[i], count });
// Store x*y in result array
result[i] *= count;
}
// Print the result
for (int i = 0; i < N; i++) {
cout << result[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1, 4 };
int N = sizeof(arr) / sizeof(int);
// Function Call
minSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to count subarrays
// for each element where it is
// the minimum
static void minSubarray(int []arr, int N)
{
int []result = new int[N];
Stack<pair> l = new Stack<>();
Stack<pair> r = new Stack<>();
// For the length of strictly larger
// numbers on the left of A[i]
for(int i = 0; i < N; i++)
{
int count = 1;
while (!l.isEmpty() &&
l.peek().first > arr[i])
{
count += l.peek().second;
l.pop();
}
l.add(new pair(arr[i], count));
// Storing x in result[i]
result[i] = count;
}
// For the length of strictly larger
// numbers on the right of A[i]
for(int i = N - 1; i >= 0; i--)
{
int count = 1;
while (!r.isEmpty() &&
r.peek().first >= arr[i])
{
count += r.peek().second;
r.pop();
}
r.add(new pair(arr[i], count));
// Store x*y in result array
result[i] *= count;
}
// Print the result
for(int i = 0; i < N; i++)
{
System.out.print(result[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1, 4 };
int N = arr.length;
// Function Call
minSubarray(arr, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the # above approach # Function to count subarrays # for each element where it is # the minimum def minSubarray(arr, N): result = [0] * N l = [] r = [] # For the length of strictly # larger numbers on the left # of A[i] for i in range(N): count = 1; while (len(l) != 0 and l[-1][0] > arr[i]): count += l[-1][1] l.pop() l.append([arr[i], count]) # Storing x in result[i] result[i] = count; # For the length of # strictly larger # numbers on the # right of A[i] for i in range(N - 1, -1, -1): count = 1; while (len(r) != 0 and r[-1][0] >= arr[i]): count += r[-1][1] r.pop(); r.append([arr[i], count]); # Store x*y in result # array result[i] *= count # Print the result for i in range(N): print(result[i], end = " ") # Driver Code if __name__ == "__main__": arr = [3, 2, 1, 4] N = len(arr) # Function Call minSubarray(arr, N) # This code is contributed by Chitranayal
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
public class pair
{
public int first,
second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
}
// Function to count subarrays
// for each element where it is
// the minimum
static void minSubarray(int []arr,
int N)
{
int []result = new int[N];
Stack<pair> l = new Stack<pair>();
Stack<pair> r = new Stack<pair>();
// For the length of strictly
// larger numbers on the left
// of A[i]
for(int i = 0; i < N; i++)
{
int count = 1;
while (l.Count != 0 &&
l.Peek().first > arr[i])
{
count += l.Peek().second;
l.Pop();
}
l.Push(new pair(arr[i],
count));
// Storing x in result[i]
result[i] = count;
}
// For the length of strictly
// larger numbers on the right
// of A[i]
for(int i = N - 1; i >= 0; i--)
{
int count = 1;
while (r.Count != 0 &&
r.Peek().first >= arr[i])
{
count += r.Peek().second;
r.Pop();
}
r.Push(new pair(arr[i],
count));
// Store x*y in result array
result[i] *= count;
}
// Print the result
for(int i = 0; i < N; i++)
{
Console.Write(result[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {3, 2, 1, 4};
int N = arr.Length;
// Function Call
minSubarray(arr, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to count subarrays
// for each element where it is
// the minimum
function minSubarray(arr,N)
{
let result = new Array(N);
for(let i=0;i<N;i++)
result[i]=0;
let l = [];
let r = [];
// For the length of strictly larger
// numbers on the left of A[i]
for(let i = 0; i < N; i++)
{
let count = 1;
while (l.length!=0 &&
l[l.length-1][0] > arr[i])
{
count += l[l.length-1][1];
l.pop();
}
l.push([arr[i], count]);
// Storing x in result[i]
result[i] = count;
}
// For the length of strictly larger
// numbers on the right of A[i]
for(let i = N - 1; i >= 0; i--)
{
let count = 1;
while (r.length!=0 &&
r[r.length-1][0] >= arr[i])
{
count += r[r.length-1][1];
r.pop();
}
r.push([arr[i], count]);
// Store x*y in result array
result[i] *= count;
}
// Print the result
for(let i = 0; i < N; i++)
{
document.write(result[i] + " ");
}
}
// Driver Code
let arr=[3, 2, 1, 4 ];
let N = arr.length;
// Function Call
minSubarray(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
1 2 6 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por NANDINIJAIN y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA