Dada una array arr que contiene N enteros positivos, la tarea es verificar si la array arr dada representa una permutación o no.
Una secuencia de N enteros se llama permutación si contiene todos los enteros del 1 al N exactamente una vez.
Ejemplos:
Entrada: arr[] = {1, 2, 5, 3, 2}
Salida: No
Explicación:
La array dada no es una permutación de números del 1 al N, porque contiene 2 dos veces y falta 4 para que la array representan una permutación de longitud 5.
Entrada: arr[] = {1, 2, 5, 3, 4}
Salida: Sí
Explicación:
La array dada contiene todos los enteros del 1 al 5 exactamente una vez. Por lo tanto, representa una permutación de longitud 5.
Enfoque ingenuo: Claramente, la array dada representará una permutación de longitud N solamente, donde N es la longitud de la array. Entonces tenemos que buscar cada elemento del 1 al N en la array dada. Si se encuentran todos los elementos, la array representa una permutación; de lo contrario, no.
Complejidad de tiempo: O(N 2 )
Enfoque eficiente:
El método anterior se puede optimizar utilizando una estructura de datos establecida .
- Recorra la array dada e inserte cada elemento en la estructura de datos establecida.
- Además, encuentre el elemento máximo en la array . Este elemento máximo será el valor N que representará el tamaño del conjunto.
- Después de atravesar la array, verifique si el tamaño del conjunto es igual a N.
- Si el tamaño del conjunto es igual a N, entonces la array representa una permutación, de lo contrario no lo es.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to decide if an
// array represents a permutation or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if an
// array represents a permutation or not
bool permutation(int arr[], int n)
{
// Set to check the count
// of non-repeating elements
set<int> hash;
int maxEle = 0;
for (int i = 0; i < n; i++) {
// Insert all elements in the set
hash.insert(arr[i]);
// Calculating the max element
maxEle = max(maxEle, arr[i]);
}
if (maxEle != n)
return false;
// Check if set size is equal to n
if (hash.size() == n)
return true;
return false;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 5, 3, 2 };
int n = sizeof(arr) / sizeof(int);
if (permutation(arr, n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java Program to decide if an
// array represents a permutation or not
import java.util.*;
class GFG{
// Function to check if an
// array represents a permutation or not
static boolean permutation(int []arr, int n)
{
// Set to check the count
// of non-repeating elements
Set<Integer> hash = new HashSet<Integer>();
int maxEle = 0;
for (int i = 0; i < n; i++) {
// Insert all elements in the set
hash.add(arr[i]);
// Calculating the max element
maxEle = Math.max(maxEle, arr[i]);
}
if (maxEle != n)
return false;
// Check if set size is equal to n
if (hash.size() == n)
return true;
return false;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 5, 3, 2 };
int n = arr.length;
if (permutation(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Surendra_Gangwar
Python3
# Python3 Program to decide if an
# array represents a permutation or not
# Function to check if an
# array represents a permutation or not
def permutation(arr, n):
# Set to check the count
# of non-repeating elements
s = set()
maxEle = 0;
for i in range(n):
# Insert all elements in the set
s.add(arr[i]);
# Calculating the max element
maxEle = max(maxEle, arr[i]);
if (maxEle != n):
return False
# Check if set size is equal to n
if (len(s) == n):
return True;
return False;
# Driver code
if __name__=='__main__':
arr = [ 1, 2, 5, 3, 2 ]
n = len(arr)
if (permutation(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by Princi Singh
C#
// C# Program to decide if an
// array represents a permutation or not
using System;
using System.Collections.Generic;
class GFG{
// Function to check if an
// array represents a permutation or not
static bool permutation(int []arr, int n)
{
// Set to check the count
// of non-repeating elements
HashSet<int> hash = new HashSet<int>();
int maxEle = 0;
for (int i = 0; i < n; i++) {
// Insert all elements in the set
hash.Add(arr[i]);
// Calculating the max element
maxEle = Math.Max(maxEle, arr[i]);
}
if (maxEle != n)
return false;
// Check if set size is equal to n
if (hash.Count == n)
return true;
return false;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 2, 5, 3, 2 };
int n = arr.Length;
if (permutation(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript Program to decide if an
// array represents a permutation or not
// Function to check if an
// array represents a permutation or not
function permutation(arr, n)
{
// Set to check the count
// of non-repeating elements
let hash = new Set();
let maxEle = 0;
for (let i = 0; i < n; i++) {
// Insert all elements in the set
hash.add(arr[i]);
// Calculating the max element
maxEle = Math.max(maxEle, arr[i]);
}
if (maxEle != n)
return false;
// Check if set size is equal to n
if (hash.length == n)
return true;
return false;
}
// Driver Code
let arr = [ 1, 2, 5, 3, 2 ];
let n = arr.length;
if (permutation(arr, n))
document.write("Yes");
else
document.write("No");
</script>
No
Complejidad de tiempo: O(N log N)
Dado que cada operación de inserción en el conjunto es una operación O (log N). Habrá N tales operaciones, por lo tanto, O (N log N).
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA