Encuentre duplicados en una array con valores de 1 a N utilizando la ordenación por conteo

Dada una array constante de N elementos que contienen elementos de 1 a N – 1 , cualquiera de estos números aparece cualquier número de veces.
Ejemplos: 
 

Entrada: N = 5, arr[] = {1, 3, 4, 2, 2} 
Salida: 2 
Explicación: 
2 es el número que aparece más de una vez.
Entrada: N = 5, arr[] = {3, 1, 3, 4, 2} 
Salida: 3 
Explicación: 
3 es el número que aparece más de una vez. 
 

Enfoque ingenuo: el método ingenuo es ordenar primero la array dada y luego buscar posiciones adyacentes de la array para encontrar el número duplicado. 
Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el método anterior, la idea es utilizar el concepto de clasificación por conteo . Dado que se conoce el rango de elementos en la array, podríamos usar esta técnica de clasificación para improvisar la complejidad del tiempo. 
La idea es inicializar otra array (digamos count[] ) con el mismo tamaño N e inicializar todos los elementos como 0 . Luego cuente las ocurrencias de cada elemento de la array y actualice el conteo en elcontar[] . Imprime todos los elementos cuyo recuento es mayor que 1 .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the duplicate
// number using counting sort method
int findDuplicate(int arr[], int n)
{
    int countArr[n + 1], i;
 
    // Initialize all the elements
    // of the countArr to 0
    for (i = 0; i <= n; i++)
        countArr[i] = 0;
 
    // Count the occurrences of each
    // element of the array
    for (i = 0; i <= n; i++)
        countArr[arr[i]]++;
 
    bool a = false;
 
    // Find the element with more
    // than one count
    for (i = 1; i <= n; i++) {
 
        if (countArr[i] > 1) {
            a = true;
            cout << i << ' ';
        }
    }
 
    // If unique elements are ther
    // print "-1"
    if (!a)
        cout << "-1";
}
 
// Driver Code
int main()
{
    // Given N
    int n = 4;
 
    // Given array arr[]
    int arr[] = { 1, 3, 4, 2, 2 };
 
    // Function Call
    findDuplicate(arr, n);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find the duplicate number
    // using counting sort method
    public static int
    findDuplicate(int arr[], int n)
    {
        int countArr[] = new int[n + 1], i;
 
        // Initialize all the elements of the
        // countArr to 0
        for (i = 0; i <= n; i++)
            countArr[i] = 0;
 
        // Count the occurrences of each
        // element of the array
        for (i = 0; i <= n; i++)
            countArr[arr[i]]++;
 
        bool a = false;
 
        // Find the element with more
        // than one count
        for (i = 1; i <= n; i++) {
 
            if (countArr[i] > 1) {
                a = true;
                System.out.print(i + " ");
            }
        }
        if (!a)
            System.out.println("-1");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        int arr[] = { 1, 3, 4, 2, 2 };
 
        // Function Call
        findDuplicate(arr, n);
    }
}

# Python3 program for the above approach
 
# Function to find the duplicate
# number using counting sort method
def findDuplicate(arr, n):
 
    # Initialize all the elements
    # of the countArr to 0
    countArr = [0] * (n + 1)
 
    # Count the occurrences of each
    # element of the array
    for i in range(n + 1):
        countArr[arr[i]] += 1
 
    a = False
 
    # Find the element with more
    # than one count
    for i in range(1, n + 1):
        if(countArr[i] > 1):
            a = True
            print(i, end = " ")
 
    # If unique elements are there
    # print "-1"
    if(not a):
        print(-1)
 
# Driver code
if __name__ == '__main__':
 
    # Given N
    n = 4
 
    # Given array arr[]
    arr = [ 1, 3, 4, 2, 2 ]
 
    # Function Call
    findDuplicate(arr, n)
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the duplicate number
// using counting sort method
static void findDuplicate(int []arr, int n)
{
    int []countArr = new int[n + 1];
    int i;
 
    // Initialize all the elements of the
    // countArr to 0
    for(i = 0; i <= n; i++)
       countArr[i] = 0;
 
    // Count the occurrences of each
    // element of the array
    for(i = 0; i <= n; i++)
       countArr[arr[i]]++;
 
    bool a = false;
 
    // Find the element with more
    // than one count
    for(i = 1; i <= n; i++)
    {
       if (countArr[i] > 1)
       {
           a = true;
           Console.Write(i + " ");
        }
    }
    if (!a)
        Console.WriteLine("-1");
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4;
    int []arr = { 1, 3, 4, 2, 2 };
 
    // Function Call
    findDuplicate(arr, n);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program for the above approach
 
    // Function to find the duplicate number
    // using counting sort method
    function
    findDuplicate(arr, n)
    {
        let countArr = Array.from({length: n+1}, (_, i) => 0), i;
 
        // Initialize all the elements of the
        // countArr to 0
        for (i = 0; i <= n; i++)
            countArr[i] = 0;
 
        // Count the occurrences of each
        // element of the array
        for (i = 0; i <= n; i++)
            countArr[arr[i]]++;
 
        let a = false;
 
        // Find the element with more
        // than one count
        for (i = 1; i <= n; i++) {
 
            if (countArr[i] > 1) {
                a = true;
                document.write(i + " ");
            }
        }
        if (!a)
            document.write("-1");
    }
 
// Driver Code
 
        let n = 4;
        let arr = [ 1, 3, 4, 2, 2 ];
 
        // Function Call
        findDuplicate(arr, n);
 
</script>

2

Tiempo Complejidad: O(N)  
Espacio Auxiliar: O(N)
Artículos relacionados: 
 

1. Encuentra duplicados en tiempo O(n) y espacio extra O(1) | Serie 1
2. Duplica en una array en O(n) y usando O(1) espacio extra | Conjunto-2