Dada una array A[] de tamaño N , la tarea es encontrar el elemento mínimo presente en todos los subarreglos para todos los tamaños de 1 a N donde todos los elementos de la array están en el rango de 1 a N
Ejemplos:
Entrada: A[ ] = {1, 2, 3}
Salida: [-1, 2, 1]
Explicación: Todos los subarreglos de tamaño 1 {{1}, {2}, {3}} no hay un valor común
para los subarreglos de tamaño 2 {{1, 2}, {2, 3}} el elemento común mínimo es 2
Para subarreglos de tamaño 3 {{1, 2, 3}} el elemento común mínimo es 1 Por lo tanto, ans=[-1, 2, 1]Entrada: A[ ] = {1, 2, 1, 3, 1}
Salida: [-1, 1, 1, 1, 1]
Enfoque ingenuo: la idea básica para resolver el problema es encontrar todos los subarreglos para todos los tamaños en el rango [1, N] . Ahora, para todos los subarreglos del mismo tamaño, encuentre el mínimo elemento común en esos subarreglos. Siga los pasos que se mencionan a continuación para resolver el problema:
- Iterar un bucle de i = 1 a N :
- Cree todos los subarreglo posibles de tamaño i .
- Cuente la frecuencia de cada elemento en todos los subarreglos.
- Compruebe si la aparición de cualquier elemento es igual al número total de subarreglos de ese tamaño
- Almacene el primer elemento que cumpla las condiciones anteriores
- Devuelve la array resultante de los elementos comunes mínimos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the minimum element array
// from size 1 to N
vector<int> Calculate_Min_array(vector<int>& A,
int N)
{
// Minimum element array(ans)
// Count array for every subsegment(cnt)
// Total occurrence array in all
// subsegment of a given size(res)
vector<int> ans(N + 1, -1), cnt(N + 1, 0),
res(N + 1, 0);
for (int i = 1; i <= N; i++) {
// Counting all the elements
// for every subsegment of size i
for (int j = 0; j < N - i + 1;
j++) {
for (int k = j; k < j + i;
k++) {
cnt[A[k]]++;
}
// If count of element is
// greater than 0 then
// increment its occurrence
for (int k = 1; k <= N; k++) {
if (cnt[k]) {
// If element is present
// increase its count
res[k]++;
cnt[k] = 0;
}
}
}
// When occurrence of an element
// is equal to total subsegment
// of size i then we will get the
// desired val for that subsegment
for (int j = 1; j <= N; j++) {
if (res[j] == (N - i + 1)) {
ans[i] = j;
break;
}
res[j] = 0;
}
}
// Final array
return ans;
}
// Print Function
void print(vector<int> vec, int N)
{
vector<int> ans
= Calculate_Min_array(vec, N);
// Output
for (int i = 1; i <= N; i++)
cout << ans[i] << " ";
cout << "\n";
}
// Driver code
int main()
{
// Initialization of array
vector<int> A = { 1, 2, 3 };
int N = 3;
// Calling function
print(A, N);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate
// the minimum element array
// from size 1 to N
public static int[] Calculate_Min_array(int A[], int N)
{
// Minimum element array(ans)
// Count array for every subsegment(cnt)
// Total occurrence array in all
// subsegment of a given size(res)
int ans[] = new int[N + 1];
int cnt[] = new int[N + 1];
int res[] = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
ans[i] = -1;
}
for (int i = 1; i <= N; i++) {
// Counting all the elements
// for every subsegment of size i
for (int j = 0; j < N - i + 1; j++) {
for (int k = j; k < j + i; k++) {
cnt[A[k]]++;
}
// If count of element is
// greater than 0 then
// increment its occurrence
for (int k = 1; k <= N; k++) {
if (cnt[k] != 0) {
// If element is present
// increase its count
res[k]++;
cnt[k] = 0;
}
}
}
// When occurrence of an element
// is equal to total subsegment
// of size i then we will get the
// desired val for that subsegment
for (int j = 1; j <= N; j++) {
if (res[j] == (N - i + 1)) {
ans[i] = j;
break;
}
res[j] = 0;
}
}
// Final array
return ans;
}
// Print Function
public static void print(int vec[], int N)
{
int ans[] = Calculate_Min_array(vec, N);
// Output
for (int i = 1; i <= N; i++)
System.out.print(ans[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int A[] = { 1, 2, 3 };
int N = 3;
// Calling function
print(A, N);
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code for the above approach
# Function to calculate
# the minimum element array
# from size 1 to N
def Calculate_Min_array(A, N):
# Minimum element array(ans)
# Count array for every subsegment(cnt)
# Total occurrence array in all
# subsegment of a given size(res)
ans = [-1 for i in range(N + 1)]
cnt = [0 for i in range(N + 1)]
res = [0 for i in range(N + 1)]
for i in range(1, N + 1):
# Counting all the elements
# for every subsegment of size i
for j in range(N - i + 1):
for k in range(j, j + i):
cnt[A[k]] = cnt[A[k]] + 1
# If count of element is
# greater than 0 then
# increment its occurrence
for k in range(1, N + 1):
if (cnt[k]):
# If element is present
# increase its count
res[k] += 1
cnt[k] = 0
# When occurrence of an element
# is equal to total subsegment
# of size i then we will get the
# desired val for that subsegment
for j in range(1,N+1):
if (res[j] == (N - i + 1)):
ans[i] = j
break
res[j] = 0
# Final array
return ans
# Print Function
def Print(vec,N):
ans = Calculate_Min_array(vec, N)
# Output
for i in range(1,N+1):
print(ans[i] ,end = " ")
print("")
# Driver code
# Initialization of array
A = [ 1, 2, 3 ]
N = 3
# Calling function
Print(A, N)
# This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
class GFG {
// Function to calculate
// the minimum element array
// from size 1 to N
static int[] Calculate_Min_array(int[] A, int N)
{
// Minimum element array(ans)
// Count array for every subsegment(cnt)
// Total occurrence array in all
// subsegment of a given size(res)
int[] ans = new int[N + 1];
int[] cnt = new int[N + 1];
int[] res = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
ans[i] = -1;
}
for (int i = 1; i <= N; i++) {
// Counting all the elements
// for every subsegment of size i
for (int j = 0; j < N - i + 1; j++) {
for (int k = j; k < j + i; k++) {
cnt[A[k]]++;
}
// If count of element is
// greater than 0 then
// increment its occurrence
for (int k = 1; k <= N; k++) {
if (cnt[k] != 0) {
// If element is present
// increase its count
res[k]++;
cnt[k] = 0;
}
}
}
// When occurrence of an element
// is equal to total subsegment
// of size i then we will get the
// desired val for that subsegment
for (int j = 1; j <= N; j++) {
if (res[j] == (N - i + 1)) {
ans[i] = j;
break;
}
res[j] = 0;
}
}
// Final array
return ans;
}
// Print Function
static void print(int[] vec, int N)
{
int[] ans = Calculate_Min_array(vec, N);
// Output
for (int i = 1; i <= N; i++)
Console.Write(ans[i] + " ");
Console.WriteLine();
}
public static int Main()
{
int[] A = new int[] { 1, 2, 3 };
int N = 3;
// Calling function
print(A, N);
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach
// Function to calculate
// the minimum element array
// from size 1 to N
const Calculate_Min_array = (A, N) => {
// Minimum element array(ans)
// Count array for every subsegment(cnt)
// Total occurrence array in all
// subsegment of a given size(res)
let ans = new Array(N + 1).fill(-1), cnt = new Array(N + 1).fill(0),
res = new Array(N + 1).fill(0);
for (let i = 1; i <= N; i++) {
// Counting all the elements
// for every subsegment of size i
for (let j = 0; j < N - i + 1;
j++) {
for (let k = j; k < j + i;
k++) {
cnt[A[k]]++;
}
// If count of element is
// greater than 0 then
// increment its occurrence
for (let k = 1; k <= N; k++) {
if (cnt[k]) {
// If element is present
// increase its count
res[k]++;
cnt[k] = 0;
}
}
}
// When occurrence of an element
// is equal to total subsegment
// of size i then we will get the
// desired val for that subsegment
for (let j = 1; j <= N; j++) {
if (res[j] == (N - i + 1)) {
ans[i] = j;
break;
}
res[j] = 0;
}
}
// Final array
return ans;
}
// Print Function
const print = (vec, N) => {
let ans
= Calculate_Min_array(vec, N);
// Output
for (let i = 1; i <= N; i++)
document.write(`${ans[i]} `);
document.write("<br/>");
}
// Driver code
// Initialization of array
let A = [1, 2, 3];
let N = 3;
// Calling function
print(A, N);
// This code is contributed by rakeshsahni
</script>
Producción
-1 2 1
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea para resolver el problema de manera eficiente es la siguiente:
Si dos ocurrencias consecutivas de un valor A[i] es máximo x , entonces es parte de todos los subarreglos de tamaño x pero no de todos los subarreglos con tamaño menor que x .
Siga los pasos a continuación para implementar la idea anterior:
- Cree una array (digamos pos[i] ) para cada i-ésimo elemento para almacenar las posiciones del i-ésimo elemento de la array.
- Luego calcule el valor de la diferencia adyacente máxima para cada elemento.
- Iterar de i = 1 a N :
- Inicie otro ciclo desde j = máxima diferencia adyacente dos i a N :
- Si no se encuentra la respuesta para el subarreglo de tamaño j, entonces i es el elemento común mínimo para todo el subarreglo de tamaño j y continúa para valores más altos de j .
- De lo contrario, salga del ciclo porque todos los valores más altos también deben completarse
- Inicie otro ciclo desde j = máxima diferencia adyacente dos i a N :
- Devuelve la array resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the minimum element array
// from size 1 to N
vector<int> Calculate_Min_array(vector<int>& A,
int N)
{
vector<int> mx(N + 1, -1), ans(N + 1, -1);
vector<int> pos[N + 1];
// Inserting the first position
// of elements
for (int i = 1; i <= N; i++) {
pos[i].push_back(0);
}
// Inserting the diff position
// of elements
for (int i = 0; i < N; i++) {
int x = A[i];
pos[x].push_back(i + 1);
}
// Inserting the last position
// of elements
for (int i = 1; i <= N; i++) {
pos[i].push_back(N + 1);
}
// Calculating max adjacent diff
// of elements
for (int i = 1; i <= N; i++) {
for (int j = 0;
j < pos[i].size() - 1; j++) {
mx[i] = max(mx[i],
pos[i][j + 1]
- pos[i][j]);
}
}
// Calculating ans for every subarray size
for (int i = 1; i <= N; i++) {
for (int j = mx[i]; j <= N; j++) {
// If ans[j] is already present
// move to next element
if (ans[j] != -1)
break;
// Otherwise store the ans[j]=i
ans[j] = i;
}
}
// Final array
return ans;
}
// Print Function
void print(vector<int> A, int N)
{
// Calculation Minimum element array
// For Every subsegment length from
// 1 to N
vector<int> ans
= Calculate_Min_array(A, N);
// Output
for (int i = 1; i <= N; i++)
cout << ans[i] << " ";
cout << "\n";
}
// Driver code
int main()
{
int N = 3;
// Initialization of array
vector<int> A = { 1, 2, 3 };
print(A, N);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG
{
// Function to calculate
// the minimum element array
// from size 1 to N
static int[] Calculate_Min_array(int[] A, int N)
{
int mx[] = new int[N + 1];
int ans[] = new int[N + 1];
int[][] pos = new int[N + 1][N + 1];
for (int i = 0; i <= N; i++) {
mx[i] = -1;
ans[i] = -1;
}
HashMap<Integer, Integer> map = new HashMap<>();
// Inserting the first position
// of elements
for (int i = 1; i <= N; i++) {
pos[i][0] = 0;
map.put(i, 1);
}
// Inserting the diff position
// of elements
for (int i = 0; i < N; i++) {
int x = A[i];
int ind = map.get(x);
pos[x][ind] = i + 1;
map.put(x, ++ind);
}
// Inserting the last position
// of elements
for (int i = 1; i <= N; i++) {
int ind = map.get(i);
pos[i][ind] = N + 1;
map.put(i, ++ind);
}
// Calculating max adjacent diff
// of elements
for (int i = 1; i <= N; i++) {
for (int j = 0; j < map.get(i) - 1; j++) {
mx[i] = Math.max(mx[i], pos[i][j + 1]
- pos[i][j]);
}
}
// Calculating ans for every subarray size
for (int i = 1; i <= N; i++) {
for (int j = mx[i]; j <= N; j++) {
// If ans[j] is already present
// move to next element
if (ans[j] != -1)
break;
// Otherwise store the ans[j]=i
ans[j] = i;
}
}
// Final array
return ans;
}
// Print Function
static void print(int[] A, int N)
{
// Calculation Minimum element array
// For Every subsegment length from
// 1 to N
int[] ans = Calculate_Min_array(A, N);
// Output
for (int i = 1; i <= N; i++)
System.out.print(ans[i] + " ");
}
// Driver code
public static void main(String[] args)
{
// Initialization of array
int N = 3;
int A[] = { 1, 2, 3 };
// Driver code
print(A, N);
}
}
// This code is contributed by phasing17
Python3
# Python code for the above approach:
# Function to calculate
# the minimum element array
# from size 1 to N
def Calculate_Min_array(A, N):
mx, ans, pos = [-1 for i in range(N + 1)] , [-1 for i in range(N + 1)] , [[] for i in range(N + 1)]
# Inserting the first position
# of elements
for i in range(1, N + 1):
pos[i].append(0)
# Inserting the diff position
# of elements
for i in range(N):
x = A[i]
pos[x].append(i + 1)
# Inserting the last position
# of elements
for i in range(1, N + 1):
pos[i].append(N + 1)
# Calculating max adjacent diff
# of elements
for i in range(1, N + 1):
for j in range(len(pos[i]) - 1):
mx[i] = max(mx[i], pos[i][j + 1] - pos[i][j])
# Calculating ans for every subarray size
for i in range(1, N + 1):
for j in range(mx[i], N + 1):
# If ans[j] is already present
# move to next element
if (ans[j] != -1):
break
# Otherwise store the ans[j]=i
ans[j] = i
# Final array
return ans
# Print Function
def Print(A, N):
# Calculation Minimum element array
# For Every subsegment length from
# 1 to N
ans = Calculate_Min_array(A, N)
# Output
for i in range(1, N + 1):
print(ans[i], end = " ")
print("")
# Driver code
N = 3
# Initialization of array
A = [ 1, 2, 3 ]
Print(A, N)
# This code is contributed by shinjanpatra
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
public class GFG
{
// Function to calculate
// the minimum element array
// from size 1 to N
static int[] Calculate_Min_array(int[] A, int N)
{
int []mx = new int[N + 1];
int []ans = new int[N + 1];
int[,] pos = new int[N + 1,N + 1];
for (int i = 0; i <= N; i++) {
mx[i] = -1;
ans[i] = -1;
}
Dictionary<int, int> map = new Dictionary<int, int>();
// Inserting the first position
// of elements
for (int i = 1; i <= N; i++) {
pos[i,0] = 0;
map.Add(i, 1);
}
// Inserting the diff position
// of elements
for (int i = 0; i < N; i++) {
int x = A[i];
int ind = map[x];
pos[x,ind] = i + 1;
map[x] = map[x] + ind++;
}
// Inserting the last position
// of elements
for (int i = 1; i <= N; i++) {
int ind = map[i];
pos[i,ind] = N + 1;
map[i] = map[i] + ind++;
}
// Calculating max adjacent diff
// of elements
for (int i = 1; i <= N; i++) {
for (int j = 0; j < map[i] - 1; j++) {
mx[i] = Math.Max(mx[i], pos[i,j + 1]
- pos[i,j]);
}
}
// Calculating ans for every subarray size
for (int i = 1; i <= N; i++) {
for (int j = mx[i]; j <= N; j++) {
// If ans[j] is already present
// move to next element
if (ans[j] != -1)
break;
// Otherwise store the ans[j]=i
ans[j] = i;
}
}
// Final array
return ans;
}
// Print Function
static void print(int[] A, int N)
{
// Calculation Minimum element array
// For Every subsegment length from
// 1 to N
int[] ans = Calculate_Min_array(A, N);
// Output
for (int i = 1; i <= N; i++)
Console.Write(ans[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
// Initialization of array
int N = 3;
int []A = { 1, 2, 3 };
// Driver code
print(A, N);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach:
// Function to calculate
// the minimum element array
// from size 1 to N
function Calculate_Min_array(A,N)
{
let mx = new Array(N + 1).fill(-1);
let ans = new Array(N + 1).fill(-1);
let pos = new Array(N + 1);
for(let i=0;i<N + 1;i++){
pos[i] = new Array();
}
// Inserting the first position
// of elements
for (let i = 1; i <= N; i++) {
pos[i].push(0);
}
// Inserting the diff position
// of elements
for (let i = 0; i < N; i++) {
let x = A[i];
pos[x].push(i + 1);
}
// Inserting the last position
// of elements
for (let i = 1; i <= N; i++) {
pos[i].push(N + 1);
}
// Calculating max adjacent diff
// of elements
for (let i = 1; i <= N; i++) {
for (let j = 0;
j < pos[i].length - 1; j++) {
mx[i] = Math.max(mx[i],
pos[i][j + 1]
- pos[i][j]);
}
}
// Calculating ans for every subarray size
for (let i = 1; i <= N; i++) {
for (let j = mx[i]; j <= N; j++) {
// If ans[j] is already present
// move to next element
if (ans[j] != -1)
break;
// Otherwise store the ans[j]=i
ans[j] = i;
}
}
// Final array
return ans;
}
// Print Function
function print(A,N)
{
// Calculation Minimum element array
// For Every subsegment length from
// 1 to N
let ans = Calculate_Min_array(A, N);
// Output
for (let i = 1; i <= N; i++){
document.write(ans[i]," ");
}
document.write("</br>");
}
// Driver code
let N = 3;
// Initialization of array
let A = [ 1, 2, 3 ];
print(A, N)
// This code is contributed by shinjanpatra
</script>
Producción
-1 2 1
Complejidad de tiempo : O(N) Porque aunque se utilizan bucles anidados, se llenan como máximo N puntos y un punto se visita como máximo dos veces
Espacio auxiliar : O(N) Aunque se utiliza una array de vectores, pero el total de puntos almacenados es N
Publicación traducida automáticamente
Artículo escrito por rudrachhangani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA