Dada una array A[] que consta de enteros [1, N] , la tarea es contar el número total de subarreglos de todas las longitudes posibles x ( 1 ≤ x ≤ N ), que consta de una permutación de enteros [1, x] de la array dada.
Ejemplos:
Entrada: A[] = {3, 1, 2, 5, 4} Salida: 4
Explicación:
Los subarreglos que forman una permutación son {1}, {1, 2}, {3, 1, 2} y {3, 1, 2, 5, 4}.
Entrada: A[] = {4, 5, 1, 3, 2, 6} Salida: 4
Explicación:
Los subarreglos que forman una permutación son {1}, {1, 3, 2}, {4, 5, 1, 3, 2} y {4, 5, 1, 3, 2, 6}.
Enfoque ingenuo:
siga los pasos a continuación para resolver el problema:
- El enfoque más simple para resolver el problema es generar todos los subarreglos posibles .
- Para cada subarreglo, verifique si es una permutación de elementos en el rango [1, longitud del subarreglo] .
- Por cada subarreglo encontrado, aumente el conteo . Finalmente, imprima el conteo .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, siga los pasos a continuación:
- Para cada elemento de i = [1, N] , verifique el índice máximo y mínimo, en el que están presentes los elementos de la permutación [1, i] .
- Si la diferencia entre el índice máximo y mínimo es igual a i , significa que hay una permutación contigua válida para i.
- Por cada permutación, aumente el conteo . Finalmente, imprima el conteo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function returns the required count
int PermuteTheArray(int A[], int n)
{
int arr[n];
// Store the indices of the
// elements present in A[].
for (int i = 0; i < n; i++) {
arr[A[i] - 1] = i;
}
// Store the maximum and
// minimum index of the
// elements from 1 to i.
int mini = n, maxi = 0;
int count = 0;
for (int i = 0; i < n; i++) {
// Update maxi and mini, to
// store minimum and maximum
// index for permutation
// of elements from 1 to i+1
mini = min(mini, arr[i]);
maxi = max(maxi, arr[i]);
// If difference between maxi
// and mini is equal to i
if (maxi - mini == i)
// Increase count
count++;
}
// Return final count
return count;
}
// Driver Code
int main()
{
int A[] = { 4, 5, 1, 3, 2, 6 };
cout << PermuteTheArray(A, 6);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function returns the required count
static int PermuteTheArray(int A[], int n)
{
int []arr = new int[n];
// Store the indices of the
// elements present in A[].
for(int i = 0; i < n; i++)
{
arr[A[i] - 1] = i;
}
// Store the maximum and
// minimum index of the
// elements from 1 to i.
int mini = n, maxi = 0;
int count = 0;
for(int i = 0; i < n; i++)
{
// Update maxi and mini, to
// store minimum and maximum
// index for permutation
// of elements from 1 to i+1
mini = Math.min(mini, arr[i]);
maxi = Math.max(maxi, arr[i]);
// If difference between maxi
// and mini is equal to i
if (maxi - mini == i)
// Increase count
count++;
}
// Return final count
return count;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 4, 5, 1, 3, 2, 6 };
System.out.print(PermuteTheArray(A, 6));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Function returns the required count def PermuteTheArray(A, n): arr = [0] * n # Store the indices of the # elements present in A[]. for i in range(n): arr[A[i] - 1] = i # Store the maximum and # minimum index of the # elements from 1 to i. mini = n maxi = 0 count = 0 for i in range(n): # Update maxi and mini, to # store minimum and maximum # index for permutation # of elements from 1 to i+1 mini = min(mini, arr[i]) maxi = max(maxi, arr[i]) # If difference between maxi # and mini is equal to i if (maxi - mini == i): # Increase count count += 1 # Return final count return count # Driver Code if __name__ == "__main__": A = [ 4, 5, 1, 3, 2, 6 ] print(PermuteTheArray(A, 6)) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function returns the required count
static int PermuteTheArray(int []A, int n)
{
int []arr = new int[n];
// Store the indices of the
// elements present in []A.
for(int i = 0; i < n; i++)
{
arr[A[i] - 1] = i;
}
// Store the maximum and
// minimum index of the
// elements from 1 to i.
int mini = n, maxi = 0;
int count = 0;
for(int i = 0; i < n; i++)
{
// Update maxi and mini, to
// store minimum and maximum
// index for permutation
// of elements from 1 to i+1
mini = Math.Min(mini, arr[i]);
maxi = Math.Max(maxi, arr[i]);
// If difference between maxi
// and mini is equal to i
if (maxi - mini == i)
// Increase count
count++;
}
// Return final count
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 4, 5, 1, 3, 2, 6 };
Console.Write(PermuteTheArray(A, 6));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function returns the required count
function PermuteTheArray(A, n)
{
var arr = Array(n);
// Store the indices of the
// elements present in A[].
for (var i = 0; i < n; i++) {
arr[A[i] - 1] = i;
}
// Store the maximum and
// minimum index of the
// elements from 1 to i.
var mini = n, maxi = 0;
var count = 0;
for (var i = 0; i < n; i++) {
// Update maxi and mini, to
// store minimum and maximum
// index for permutation
// of elements from 1 to i+1
mini = Math.min(mini, arr[i]);
maxi = Math.max(maxi, arr[i]);
// If difference between maxi
// and mini is equal to i
if (maxi - mini == i)
// Increase count
count++;
}
// Return final count
return count;
}
// Driver Code
var A = [4, 5, 1, 3, 2, 6];
document.write( PermuteTheArray(A, 6));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA