Comprobar si un Array es una permutación de números del 1 al N

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
 

  1. Recorra la array dada e inserte cada elemento en la estructura de datos establecida.
  2. 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.
  3. Después de atravesar la array, verifique si el tamaño del conjunto es igual a N.
  4. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *