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