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

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 contiene 2 dos veces y falta 4 para que la array represente una permutación de longitud 5. 
Entrada: arr[] = {1, 2, 5, 3, 4} 
Salida: Sí 
Explicación: 
La array dada contiene todos los números enteros del 1 al 5 exactamente una vez. Por lo tanto, representa una permutación de longitud 5. 
 

Enfoque ingenuo: en tiempo O(N ² ) 
Este enfoque se menciona aquí
Otro enfoque: en tiempo O(N) y espacio O(N) 
Este enfoque se menciona aquí .
Enfoque eficiente: uso de HashTable 
 

1. Cree una HashTable de tamaño N para almacenar el conteo de frecuencia de cada número de 1 a N
2. Recorra la array dada y almacene la frecuencia de cada número en HashTable.
3. Luego recorra HashTable y verifique si todos los números del 1 al N tienen una frecuencia de 1 o no. 
4. Escriba «Sí» si la condición anterior es verdadera, de lo contrario «No».

A continuación se muestra la implementación del enfoque anterior: 
 

// 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
string permutation(int arr[], int N)
{
 
    int hash[N + 1] = { 0 };
 
    // Counting the frequency
    for (int i = 0; i < N; i++) {
        hash[arr[i]]++;
    }
 
    // Check if each frequency is 1 only
    for (int i = 1; i <= N; i++) {
        if (hash[i] != 1)
            return "No";
    }
 
    return "Yes";
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 5, 5, 3 };
    int n = sizeof(arr) / sizeof(int);
    cout << permutation(arr, n) << endl;
 
    return 0;
}

// Java program to decide if an array
// represents a permutation or not
class GFG{
  
// Function to check if an
// array represents a permutation or not
static String permutation(int arr[], int N)
{
  
    int []hash = new int[N + 1];
  
    // Counting the frequency
    for (int i = 0; i < N; i++) {
        hash[arr[i]]++;
    }
  
    // Check if each frequency is 1 only
    for (int i = 1; i <= N; i++) {
        if (hash[i] != 1)
            return "No";
    }
  
    return "Yes";
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 5, 5, 3 };
    int n = arr.length;
    System.out.print(permutation(arr, n) +"\n");
}
}
 
// This code is contributed by Princi Singh

# 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) :
 
    hash = [0]*(N + 1);
 
    # Counting the frequency
    for i in range(N) :
        hash[arr[i]] += 1;
 
    # Check if each frequency is 1 only
    for i in range(1, N + 1) :
        if (hash[i] != 1) :
            return "No";
 
    return "Yes";
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 1, 5, 5, 3 ];
    n = len(arr);
    print(permutation(arr, n));
 
    # This code is contributed by Yash_R

// C# program to decide if an array
// represents a permutation or not
using System;
 
class GFG{
  
    // Function to check if an
    // array represents a permutation or not
    static string permutation(int []arr, int N)
    {
      
        int []hash = new int[N + 1];
      
        // Counting the frequency
        for (int i = 0; i < N; i++) {
            hash[arr[i]]++;
        }
      
        // Check if each frequency is 1 only
        for (int i = 1; i <= N; i++) {
            if (hash[i] != 1)
                return "No";
        }
      
        return "Yes";
    }
      
    // Driver code
    public static void Main(string[] args)
    {
        int []arr = { 1, 1, 5, 5, 3 };
        int n = arr.Length;
        Console.Write(permutation(arr, n) +"\n");
    }
}
 
// This code is contributed by Yash_R

<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)
{
 
    var hash = Array(N+1).fill(0);
 
    // Counting the frequency
    for (var i = 0; i < N; i++) {
        hash[arr[i]]++;
    }
 
    // Check if each frequency is 1 only
    for (var i = 1; i <= N; i++) {
        if (hash[i] != 1)
            return "No";
    }
 
    return "Yes";
}
 
// Driver code
var arr = [1, 1, 5, 5, 3];
var n = arr.length;
document.write( permutation(arr, n));
 
</script>

No

Complejidad temporal: O(N)  
Complejidad espacial auxiliar: O(N)