Dada una permutación de enteros de 1 a N y un entero M , la tarea es verificar si algún subarreglo de la permutación dada es una permutación de enteros de 1 a M.
Ejemplos:
Entrada: arr[] = {4, 5, 1, 3, 2, 6}, M = 3
Salida: Sí
{4, 5, 1, 3, 2 , 6} es el subarreglo requerido.Entrada: arr[] = {4, 5, 1, 3, 2, 6}, M = 4
Salida: No
Enfoque ingenuo: un enfoque ingenuo sería generar todos los subarreglos de tamaño M y ver si existe alguno de ellos. Pero si la permutación dada es demasiado grande, este enfoque llevará mucho tiempo ya que se ejecuta en O(N 3 ).
Enfoque eficiente: una mejor solución es usar Hashing .
- A partir de la permutación principal, las posiciones de cada entero se almacenan en un mapa/diccionario .
- Ahora, observe que si existe un subarreglo que es una permutación de 1 a m, entonces todos los números en el rango [1, m] ocuparán m lugares consecutivos en la permutación principal, ya sea de manera ordenada o aleatoria.
- Sus posiciones también deben aparecer como m-números consecutivos, cuando se ordenan, comenzando con la posición/valor mínimo x, y sus m-1 posiciones consecutivas.
- Por lo tanto , se puede calcular la ‘suma de posiciones’ para cada entero de 1 a n, donde sum_of_position(k) = sumcur= Position_of_1 + Position_of_2 + …Position_of_k .
- Sea x el elemento mínimo de la serie anterior . Cuando se ordenen las posiciones, este será el primer elemento y el resto serán consecutivos.
- Entonces, si existe el subarreglo requerido , entonces sum_of_position(m) tiene que ser x + (x+1) + ..(x+m-1) {m términos consecutivos} = x*m – m + m*(m+1 )/2 .
- Si la suma de todas las posiciones para los números enteros de 1 a m es esta suma, entonces para m dado, se devuelve verdadero, de lo contrario no existe tal subarreglo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Function that returns true if the
// required subarray exists
// in the given array
bool subArray(ll* arr, ll n, ll m)
{
ll i;
// Map to store the positions of
// each integer in the original
// permutation
unordered_map<ll, ll> mp;
for (i = 0; i < n; i++) {
// To store the address of each
// entry in arr[n] but with
// 1-based indexing
mp[arr[i]] = i + 1;
}
ll sumcur = 0;
// To track minimum position sumcur
// for sum of all positions
// till this position
ll p = INT_MAX;
vector<ll> ans;
for (i = 1; i <= m; i++) {
// Summing up addresses
sumcur += mp[i];
// Tracking minimum address
// encountered till now
p = min(p, mp[i]);
// The sum of the addresses if
// it forms the required subarray
ll val = p * i - i + (i * (i + 1)) / 2;
if (i == m) {
// If current sum of address
// is equal to val
if (val == sumcur) {
return true;
}
else
return false;
}
}
}
// Driver code
int main()
{
ll arr[] = { 4, 5, 1, 3, 2, 6 };
int n = sizeof(arr) / sizeof(int);
ll m = 3;
if (subArray(arr, n, m))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true if the
// required subarray exists
// in the given array
static boolean subArray(int[] arr, int n, int m)
{
int i;
// Map to store the positions of
// each integer in the original
// permutation
HashMap<Integer, Integer> mp =
new HashMap<Integer, Integer> ();
for (i = 0; i < n; i++)
{
// To store the address of each
// entry in arr[n] but with
// 1-based indexing
mp.put(arr[i], i + 1);
}
int sumcur = 0;
// To track minimum position sumcur
// for sum of aint positions
// tiint this position
int p = Integer.MAX_VALUE;
Vector<Integer> ans = new Vector<Integer>();
for (i = 1; i <= m; i++)
{
// Summing up addresses
sumcur += mp.get(i);
// Tracking minimum address
// encountered tiint now
p = Math.min(p, mp.get(i));
// The sum of the addresses if
// it forms the required subarray
int val = p * i - i + (i * (i + 1)) / 2;
if (i == m)
{
// If current sum of address
// is equal to val
if (val == sumcur)
{
return true;
}
else
return false;
}
}
return false;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 1, 3, 2, 6 };
int n = arr.length;
int m = 3;
if (subArray(arr, n, m))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Function that returns true if the
# required subarray exists
# in the given array
def subArray(arr, n, m):
i = 0
# Map to store the positions of
# each integer in the original
# permutation
mp = dict()
for i in range(n):
# To store the address of each
# entry in arr[n] but with
# 1-based indexing
mp[arr[i]] = i + 1
sumcur = 0
# To track minimum position sumcur
# for sum of a positions
# ti this position
p = 10**9
ans = []
for i in range(1, m + 1):
# Summing up addresses
sumcur += mp[i]
# Tracking minimum address
# encountered ti now
p = min(p, mp[i])
# The sum of the addresses if
# it forms the required subarray
val = p * i - i + (i * (i + 1)) / 2
if (i == m):
# If current sum of address
# is equal to val
if (val == sumcur):
return True
else:
return False
# Driver code
arr = [4, 5, 1, 3, 2, 6]
n = len(arr)
m = 3
if (subArray(arr, n, m)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function that returns true if the
// required subarray exists
// in the given array
static bool subArray(int[] arr, int n, int m)
{
int i;
// Map to store the positions of
// each integer in the original
// permutation
Dictionary<int, int> mp =
new Dictionary<int, int> ();
for (i = 0; i < n; i++)
{
// To store the address of each
// entry in arr[n] but with
// 1-based indexing
mp.Add(arr[i], i + 1);
}
int sumcur = 0;
// To track minimum position sumcur
// for sum of aint positions
// tiint this position
int p = int.MaxValue;
List<int> ans = new List<int>();
for (i = 1; i <= m; i++)
{
// Summing up addresses
sumcur += mp[i];
// Tracking minimum address
// encountered tiint now
p = Math.Min(p, mp[i]);
// The sum of the addresses if
// it forms the required subarray
int val = p * i - i + (i * (i + 1)) / 2;
if (i == m)
{
// If current sum of address
// is equal to val
if (val == sumcur)
{
return true;
}
else
return false;
}
}
return false;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 4, 5, 1, 3, 2, 6 };
int n = arr.Length;
int m = 3;
if (subArray(arr, n, m))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if the
// required subarray exists
// in the given array
function subArray(arr, n, m)
{
var i;
// Map to store the positions of
// each integer in the original
// permutation
var mp = new Map();
for(i = 0; i < n; i++)
{
// To store the address of each
// entry in arr[n] but with
// 1-based indexing
mp.set(arr[i], i + 1);
}
var sumcur = 0;
// To track minimum position sumcur
// for sum of all positions
// till this position
var p = 1000000000;
var ans = [];
for(i = 1; i <= m; i++)
{
// Summing up addresses
sumcur += mp.get(i);
// Tracking minimum address
// encountered till now
p = Math.min(p, mp.get(i));
// The sum of the addresses if
// it forms the required subarray
var val = p * i - i +
parseInt((i * (i + 1)) / 2);
if (i == m)
{
// If current sum of address
// is equal to val
if (val == sumcur)
{
return true;
}
else
return false;
}
}
}
// Driver code
var arr = [ 4, 5, 1, 3, 2, 6 ];
var n = arr.length;
var m = 3;
if (subArray(arr, n, m))
document.write("Yes");
else
document.write("No");
// This code is contributed by famously
</script>
Producción:
Yes
Complejidad de tiempo: O(N)
Otro enfoque eficiente: usar la ventana deslizante
Usaremos una ventana deslizante de tamaño M en la que mantendremos un recuento de números menores o iguales a M e iteraremos sobre la array. Si la cuenta se vuelve igual a M, hemos encontrado la permutación.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Function that returns true if the
// required subarray exists
// in the given array
bool subArray(ll* arr, ll n, ll m)
{
int count = 0;//count less than m
for (int i = 0; i < m; i++){
if (arr[i] <= m)
count++;
}
if (count == m)
return true;
for (int i = m; i < n; i++){
if (arr[i-m] <= m)
count--;
if (arr[i] <= m)
count++;
if (count == m)
return true;
}
return false;
}
// Driver code
int main()
{
ll arr[] = { 4, 5, 1, 3, 2, 6 };
int n = sizeof(arr) / sizeof(int);
ll m = 3;
if (subArray(arr, n, m))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
// Function that returns true if the
// required subarray exists
// in the given array
static boolean subArray(int[] arr, int n, int m)
{
int count = 0; // count less than m
for (int i = 0; i < m; i++) {
if (arr[i] <= m)
count++;
}
if (count == m)
return true;
for (int i = m; i < n; i++) {
if (arr[i - m] <= m)
count--;
if (arr[i] <= m)
count++;
if (count == m)
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 1, 3, 2, 6 };
int n = arr.length;
int m = 3;
if (subArray(arr, n, m))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by subhammahato348.
Python3
# Python3 implementation of the approach
# Function that returns true if the
# required subarray exists
# in the given array
def subArray(arr, n, m):
count = 0 # count less than m
for i in range(m):
if (arr[i] <= m):
count += 1
if (count == m):
return True
for i in range(m,n):
if (arr[i-m] <= m):
count -= 1
if (arr[i] <= m):
count += 1
if (count == m):
return True
return False
# Driver code
arr = [ 4, 5, 1, 3, 2, 6 ]
n = len(arr)
m = 3
if (subArray(arr, n, m)):
print("Yes")
else:
print("No")
# This code is contributed by shinjanpatra
C#
// C# implementation of the approach
using System;
class GFG {
// Function that returns true if the
// required subarray exists
// in the given array
static bool subArray(int[] arr, int n, int m)
{
int count = 0; // count less than m
for (int i = 0; i < m; i++) {
if (arr[i] <= m)
count++;
}
if (count == m)
return true;
for (int i = m; i < n; i++) {
if (arr[i - m] <= m)
count--;
if (arr[i] <= m)
count++;
if (count == m)
return true;
}
return false;
}
// Driver code
public static void Main()
{
int[] arr = { 4, 5, 1, 3, 2, 6 };
int n = arr.Length;
int m = 3;
if (subArray(arr, n, m))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if the
// required subarray exists
// in the given array
function subArray(arr, n, m)
{
let count = 0//count less than m
for (let i = 0; i < m; i++){
if (arr[i] <= m)
count++;
}
if (count == m)
return true;
for (let i = m; i < n; i++){
if (arr[i-m] <= m)
count--;
if (arr[i] <= m)
count++;
if (count == m)
return true;
}
return false;
}
// Driver code
let arr =[ 4, 5, 1, 3, 2, 6 ]
let n = arr.length
let m = 3
if (subArray(arr, n, m))
document.write("Yes")
else
document.write("No")
// This code is contributed by shinjanpatra
</script>
Complejidad de tiempo: O(N)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA