Contar subarrayes para cada elemento da array em que sejam o mínimo
Dado um array arr [] consistindo em N inteiros, a tarefa é criar um array brr [] de tamanho N onde brr [i] representa a contagem de subarrayes em que arr [i] é o menor elemento.
Exemplos:
Entrada: arr [] = {3, 2, 4}
Saída: {1, 3, 1}
Explicação:
Para arr [0], há apenas um subarray em que 3 é o menor ({3}).
Para arr [1], existem três subarrayes, onde 2 é o menor ({2}, {3, 2}, {2, 4}).
Para arr [2], há apenas um subarray em que 4 é o menor ({4}).Entrada: arr [] = {1, 2, 3, 4, 5}
Saída: {5, 4, 3, 2, 1}
Abordagem ingênua: A abordagem mais simples é gerar todos os subarranjos de um determinado array e, para cada elemento do array arr [i] , contar o número de subarrayes nos quais é o menor elemento.
Complexidade de tempo: O (N 3 )
Espaço auxiliar: O (N)
Abordagem Eficiente: Para otimizar a abordagem acima, a ideia é encontrar o índice de fronteira para cada elemento, até o qual é o menor elemento. Para cada elemento, sejam L e R os índices de contorno do lado esquerdo e direito, respectivamente, até o qual arr [i] é o mínimo. Portanto, a contagem de todos os subarrays pode ser calculada por:
(L + R + 1) * (R + 1)
Siga as etapas abaixo para resolver o problema:
- Armazene todos os índices de elementos do array em um mapa .
- Classifique a array em ordem crescente .
- Inicialize um limite de array [] .
- Itere sobre a array classificada arr [] e simplesmente insira o índice desse elemento usando a Pesquisa Binária . Suponha que ele foi inserido no índice i , então seu limite esquerdo é o limite [i - 1] e seu limite direito é o limite [i + 1] .
- Agora, usando a fórmula acima, encontre o número de subarrayes e acompanhe essa contagem na array resultante.
- Depois de concluir as etapas acima, imprima todas as contagens armazenadas na array resultante.
Abaixo está a implementação da abordagem acima:
// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the boundary of every
// element within which it is minimum
int binaryInsert(vector<int> &boundary, int i)
{
int l = 0;
int r = boundary.size() - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if (boundary[m] < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.insert(boundary.begin() + l, i);
return l;
}
// Function to required count subarrays
vector<int> countingSubarray(vector<int> arr, int n)
{
// Stores the indices of element
unordered_map<int, int> index;
for(int i = 0; i < n; i++)
index[arr[i]] = i;
vector<int> boundary = {-1, n};
sort(arr.begin(), arr.end());
// Initialize the output array
vector<int> ans(n, 0);
for(int num : arr)
{
int i = binaryInsert(boundary, index[num]);
// Left boundary, till the
// element is smallest
int l = boundary[i] - boundary[i - 1] - 1;
// Right boundary, till the
// element is smallest
int r = boundary[i + 1] - boundary[i] - 1;
// Calculate the number of subarrays
// based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index[num]] += cnt;
}
return ans;
}
// Driver Code
int main()
{
int N = 5;
// Given array arr[]
vector<int> arr = { 3, 2, 4, 1, 5 };
// Function call
auto a = countingSubarray(arr, N);
cout << "[";
int n = a.size() - 1;
for(int i = 0; i < n; i++)
cout << a[i] << ", ";
cout << a[n] << "]";
return 0;
}
// This code is contributed by mohit kumar 29// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the boundary of every
// element within which it is minimum
static int binaryInsert(ArrayList<Integer> boundary,
int i)
{
int l = 0;
int r = boundary.size() - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if (boundary.get(m) < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.add(l, i);
return l;
}
// Function to required count subarrays
static int[] countingSubarray(int[] arr,
int n)
{
// Stores the indices of element
Map<Integer, Integer> index = new HashMap<>();
for(int i = 0; i < n; i++)
index.put(arr[i], i);
ArrayList<Integer> boundary = new ArrayList<>();
boundary.add(-1);
boundary.add(n);
Arrays.sort(arr);
// Initialize the output array
int[] ans = new int[n];
for(int num : arr)
{
int i = binaryInsert(boundary,
index.get(num));
// Left boundary, till the
// element is smallest
int l = boundary.get(i) -
boundary.get(i - 1) - 1;
// Right boundary, till the
// element is smallest
int r = boundary.get(i + 1) -
boundary.get(i) - 1;
// Calculate the number of subarrays
// based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index.get(num)] += cnt;
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int N = 5;
// Given array arr[]
int[] arr = { 3, 2, 4, 1, 5 };
// Function call
int[] a = countingSubarray(arr, N);
System.out.print("[");
int n = a.length - 1;
for(int i = 0; i < n; i++)
System.out.print(a[i] + ", ");
System.out.print(a[n] + "]");
}
}
// This code is contributed by offbeat# Python3 program for the above approach
# Function to find the boundary of every
# element within which it is minimum
def binaryInsert(boundary, i):
l = 0
r = len(boundary) - 1
# Perform Binary Search
while l <= r:
# Find mid m
m = (l + r) // 2
# Update l
if boundary[m] < i:
l = m + 1
# Update r
else:
r = m - 1
# Inserting the index
boundary.insert(l, i)
return l
# Function to required count subarrays
def countingSubarray(arr, n):
# Stores the indices of element
index = {}
for i in range(n):
index[arr[i]] = i
boundary = [-1, n]
arr.sort()
# Initialize the output array
ans = [0 for i in range(n)]
for num in arr:
i = binaryInsert(boundary, index[num])
# Left boundary, till the
# element is smallest
l = boundary[i] - boundary[i - 1] - 1
# Right boundary, till the
# element is smallest
r = boundary[i + 1] - boundary[i] - 1
# Calculate the number of subarrays
# based on its boundary
cnt = l + r + l * r + 1
# Adding cnt to the ans
ans[index[num]] += cnt
return ans
# Driver Code
N = 5
# Given array arr[]
arr = [3, 2, 4, 1, 5]
# Function Call
print(countingSubarray(arr, N))// C# program for
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find the
// boundary of every element
// within which it is minimum
static int binaryInsert(ArrayList boundary,
int i)
{
int l = 0;
int r = boundary.Count - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if ((int)boundary[m] < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.Insert(l, i);
return l;
}
// Function to required count subarrays
static int[] countingSubarray(int[] arr,
int n)
{
// Stores the indices of element
Dictionary<int,
int> index = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
index[arr[i]] = i;
ArrayList boundary = new ArrayList();
boundary.Add(-1);
boundary.Add(n);
Array.Sort(arr);
// Initialize the output array
int[] ans = new int[n];
foreach(int num in arr)
{
int i = binaryInsert(boundary,
index[num]);
// Left boundary, till the
// element is smallest
int l = (int)boundary[i] -
(int)boundary[i - 1] - 1;
// Right boundary, till the
// element is smallest
int r = (int)boundary[i + 1] -
(int)boundary[i] - 1;
// Calculate the number of
// subarrays based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index[num]] += cnt;
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 5;
// Given array arr[]
int[] arr = {3, 2, 4, 1, 5};
// Function call
int[] a = countingSubarray(arr, N);
Console.Write("[");
int n = a.Length - 1;
for(int i = 0; i < n; i++)
Console.Write(a[i] + ", ");
Console.Write(a[n] + "]");
}
}
// This code is contributed by Rutvik_56Saída
[1, 4, 1, 8, 1]
Complexidade de tempo: O (N log N)
Espaço auxiliar: O (N)
Abordagem mais eficiente:
Para otimizar a abordagem acima, podemos usar uma estrutura de dados de pilha.
- A ideia é que, para cada (1≤ i ≤ N), tentaremos encontrar o índice (R) do próximo elemento menor à direita dele e o índice (L) do próximo elemento menor à esquerda dele.
- Agora temos nosso índice de fronteira (L, R) em que arr [i] é mínimo, então o número total de subarrays para cada i (base 0) será (Ri) * (iL).
Abaixo está a implementação da ideia:
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to required count subarrays
vector<int> countingSubarray(vector<int> arr, int n)
{
// For storing count of subarrays
vector<int> a(n);
// For finding next smaller
// element left to a element
// if there is no next smaller
// element left to it than taking -1.
vector<int> nsml(n, -1);
// For finding next smaller
// element right to a element
// if there is no next smaller
// element right to it than taking n.
vector<int> nsmr(n, n);
stack<int> st;
for (int i = n - 1; i >= 0; i--)
{
while (!st.empty() && arr[st.top()] >= arr[i])
st.pop();
nsmr[i] = (!st.empty()) ? st.top() : n;
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = 0; i < n; i++)
{
while (!st.empty() && arr[st.top()] >= arr[i])
st.pop();
nsml[i] = (!st.empty()) ? st.top() : -1;
st.push(i);
}
for (int i = 0; i < n; i++)
{
// Taking exact boundaries
// in which arr[i] is
// minimum
nsml[i]++;
// Similarly for right side
nsmr[i]--;
int r = nsmr[i] - i + 1;
int l = i - nsml[i] + 1;
a[i] = r * l;
}
return a;
}
// Driver Code
int main()
{
int N = 5;
// Given array arr[]
vector<int> arr = { 3, 2, 4, 1, 5 };
// Function call
auto a = countingSubarray(arr, N);
cout << "[";
int n = a.size() - 1;
for (int i = 0; i < n; i++)
cout << a[i] << ", ";
cout << a[n] << "]";
return 0;
}// Java implementation of the above approach
import java.util.*;
public class gfg
{
// Function to required count subarrays
static int[] countingSubarray(int arr[], int n)
{
// For storing count of subarrays
int a[] = new int[n];
// For finding next smaller
// element left to a element
// if there is no next smaller
// element left to it than taking -1.
int nsml[] = new int[n];
Arrays.fill(nsml, -1);
// For finding next smaller
// element right to a element
// if there is no next smaller
// element right to it than taking n.
int nsmr[] = new int[n];
Arrays.fill(nsmr, n);
Stack<Integer> st = new Stack<Integer>();
for(int i = n - 1; i >= 0; i--)
{
while (st.size() > 0 &&
arr[(int)st.peek()] >= arr[i])
st.pop();
nsmr[i] = (st.size() > 0) ? (int)st.peek() : n;
st.push(i);
}
while (st.size() > 0)
st.pop();
for(int i = 0; i < n; i++)
{
while (st.size() > 0 &&
arr[(int)st.peek()] >= arr[i])
st.pop();
nsml[i] = (st.size() > 0) ? (int)st.peek() : -1;
st.push(i);
}
for(int i = 0; i < n; i++)
{
// Taking exact boundaries
// in which arr[i] is
// minimum
nsml[i]++;
// Similarly for right side
nsmr[i]--;
int r = nsmr[i] - i + 1;
int l = i - nsml[i] + 1;
a[i] = r * l;
}
return a;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
// Given array arr[]
int arr[] = { 3, 2, 4, 1, 5 };
// Function call
int a[] = countingSubarray(arr, N);
System.out.print("[");
int n = a.length - 1;
for(int i = 0; i < n; i++)
System.out.print(a[i] + ", ");
System.out.print(a[n] + "]");
}
}
// This code is contributed by divyesh072019.# Python implementation of the above approach
# Function to required count subarrays
def countingSubarray(arr, n):
# For storing count of subarrays
a = [0 for i in range(n)]
# For finding next smaller
# element left to a element
# if there is no next smaller
# element left to it than taking -1.
nsml = [-1 for i in range(n)]
# For finding next smaller
# element right to a element
# if there is no next smaller
# element right to it than taking n.
nsmr = [n for i in range(n)]
st = []
for i in range(n - 1, -1, -1):
while(len(st) > 0 and arr[st[-1]] >= arr[i]):
del st[-1]
if(len(st) > 0):
nsmr[i] = st[-1]
else:
nsmr[i] = n
st.append(i)
while(len(st) > 0):
del st[-1]
for i in range(n):
while(len(st) > 0 and arr[st[-1]] >= arr[i]):
del st[-1]
if(len(st) > 0):
nsml[i] = st[-1]
else:
nsml[i] = -1
st.append(i)
for i in range(n):
# Taking exact boundaries
# in which arr[i] is
# minimum
nsml[i] += 1
# Similarly for right side
nsmr[i] -= 1
r = nsmr[i] - i + 1;
l = i - nsml[i] + 1;
a[i] = r * l;
return a;
# Driver code
N = 5
# Given array arr[]
arr = [3, 2, 4, 1, 5 ]
# Function call
a = countingSubarray(arr, N)
print(a)
# This code is contributed by rag2127// C# implementation of the above approach
using System;
using System.Collections;
class GFG{
// Function to required count subarrays
static int[] countingSubarray(int[] arr, int n)
{
// For storing count of subarrays
int[] a = new int[n];
// For finding next smaller
// element left to a element
// if there is no next smaller
// element left to it than taking -1.
int[] nsml = new int[n];
Array.Fill(nsml, -1);
// For finding next smaller
// element right to a element
// if there is no next smaller
// element right to it than taking n.
int[] nsmr = new int[n];
Array.Fill(nsmr, n);
Stack st = new Stack();
for(int i = n - 1; i >= 0; i--)
{
while (st.Count > 0 &&
arr[(int)st.Peek()] >= arr[i])
st.Pop();
nsmr[i] = (st.Count > 0) ? (int)st.Peek() : n;
st.Push(i);
}
while (st.Count > 0)
st.Pop();
for(int i = 0; i < n; i++)
{
while (st.Count > 0 &&
arr[(int)st.Peek()] >= arr[i])
st.Pop();
nsml[i] = (st.Count > 0) ? (int)st.Peek() : -1;
st.Push(i);
}
for(int i = 0; i < n; i++)
{
// Taking exact boundaries
// in which arr[i] is
// minimum
nsml[i]++;
// Similarly for right side
nsmr[i]--;
int r = nsmr[i] - i + 1;
int l = i - nsml[i] + 1;
a[i] = r * l;
}
return a;
}
// Driver code
static void Main()
{
int N = 5;
// Given array arr[]
int[] arr = { 3, 2, 4, 1, 5 };
// Function call
int[] a = countingSubarray(arr, N);
Console.Write("[");
int n = a.Length - 1;
for(int i = 0; i < n; i++)
Console.Write(a[i] + ", ");
Console.Write(a[n] + "]");
}
}
// This code is contributed by divyeshrabadiya07<script>
// Javascript implementation of the above approach
// Function to required count subarrays
function countingSubarray(arr, n)
{
// For storing count of subarrays
let a = new Array(n);
// For finding next smaller
// element left to a element
// if there is no next smaller
// element left to it than taking -1.
let nsml = new Array(n);
nsml.fill(-1);
// For finding next smaller
// element right to a element
// if there is no next smaller
// element right to it than taking n.
let nsmr = new Array(n);
nsmr.fill(n);
let st = [];
for(let i = n - 1; i >= 0; i--)
{
while (st.length > 0 && arr[st[st.length-1]] >= arr[i])
st.pop();
nsmr[i] = (st.length > 0) ? st[st.length-1] : n;
st.push(i);
}
while (st.length > 0)
st.pop();
for(let i = 0; i < n; i++)
{
while (st.length > 0 &&
arr[st[st.length-1]] >= arr[i])
st.pop();
nsml[i] = (st.length > 0) ? st[st.length-1] : -1;
st.push(i);
}
for(let i = 0; i < n; i++)
{
// Taking exact boundaries
// in which arr[i] is
// minimum
nsml[i]++;
// Similarly for right side
nsmr[i]--;
let r = nsmr[i] - i + 1;
let l = i - nsml[i] + 1;
a[i] = r * l;
}
return a;
}
let N = 5;
// Given array arr[]
let arr = [ 3, 2, 4, 1, 5 ];
// Function call
let a = countingSubarray(arr, N);
document.write("[");
let n = a.length - 1;
for(let i = 0; i < n; i++)
document.write(a[i] + ", ");
document.write(a[n] + "]");
// This code is contributed by rameshtravel07.
</script>Saída
[1, 4, 1, 8, 1]
Complexidade de tempo: O (N)
Espaço auxiliar: O (N)
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
