Duplica en una array en O(n) y usando O(1) espacio extra | Conjunto-2

Dada una array de n elementos que contienen elementos de 0 a n-1, con cualquiera de estos números que aparece cualquier número de veces, encuentre estos números repetidos en O (n) y use solo espacio de memoria constante.

Ejemplo:

Input: n = 7 , array = {1, 2, 3, 1, 3, 6, 6}
Output: 1, 3 and 6.
Explanation: Duplicate element in the array are 1 , 3 and 6

Input: n = 6, array = {5, 3, 1, 3, 5, 5}
Output: 3 and 5.
Explanation: Duplicate element in  the array are 3 and 6

Hemos discutido un enfoque para esta pregunta en la publicación a continuación: 
Duplicados en una array en O (n) y usando O (1) espacio adicional | Conjunto-2 . 
Pero hay un problema en el enfoque anterior. Imprime el número repetido más de una vez.

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Enfoque: La idea básica es usar un HashMap para resolver el problema. Pero hay un problema, los números en la array van del 0 al n-1, y la array de entrada tiene una longitud n. Entonces, la array de entrada se puede usar como HashMap. Mientras se recorre la array, si se encuentra un elemento a , aumente el valor de un %n ‘ésimo elemento en n. La frecuencia se puede recuperar dividiendo el elemento a%n ‘th por n.

Algoritmo:  

1. Recorre la array dada de principio a fin.
2. Para cada elemento de la array, incremente el elemento arr[i]%n ‘th en n.
3. Ahora recorra la array nuevamente e imprima todos aquellos índices i para los cuales arr[i]/n es mayor que 1. Lo que garantiza que el número n se haya agregado a ese índice.

Nota: este enfoque funciona porque todos los elementos están en el rango de 0 a n-1 y arr[i]/n sería mayor que 1 solo si ha aparecido un valor «i» más de una vez. 

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

// C++ program to print all elements that
// appear more than once.
#include <iostream>
using namespace std;
 
// function to find repeating elements
void printRepeating(int arr[], int n)
{
    // First check all the values that are
    // present in an array then go to that
    // values as indexes and increment by
    // the size of array
    for (int i = 0; i < n; i++)
    {
        int index = arr[i] % n;
        arr[index] += n;
    }
 
    // Now check which value exists more
    // than once by dividing with the size
    // of array
    for (int i = 0; i < n; i++)
    {
        if ((arr[i] / n) >= 2)
            cout << i << " ";
    }
}
 
// Driver code
int main()
{
    int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    cout << "The repeating elements are: \n";
 
    // Function call
    printRepeating(arr, arr_size);
    return 0;
}

// Java program to print all elements that
// appear more than once.
import java.util.*;
class GFG {
 
    // function to find repeating elements
    static void printRepeating(int arr[], int n)
    {
        // First check all the values that are
        // present in an array then go to that
        // values as indexes and increment by
        // the size of array
        for (int i = 0; i < n; i++)
        {
            int index = arr[i] % n;
            arr[index] += n;
        }
 
        // Now check which value exists more
        // than once by dividing with the size
        // of array
        for (int i = 0; i < n; i++)
        {
            if ((arr[i] / n) >= 2)
                System.out.print(i + " ");
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
        int arr_size = arr.length;
 
        System.out.println("The repeating elements are: ");
 
        // Function call
        printRepeating(arr, arr_size);
    }
}

# Python3 program to
# print all elements that
# appear more than once.
 
# function to find
# repeating elements
 
 
def printRepeating(arr, n):
 
    # First check all the
        # values that are
    # present in an array
        # then go to that
    # values as indexes
        # and increment by
    # the size of array
    for i in range(0, n):
        index = arr[i] % n
        arr[index] += n
 
    # Now check which value
        # exists more
    # than once by dividing
        # with the size
    # of array
    for i in range(0, n):
        if (arr[i]/n) >= 2:
            print(i, end=" ")
 
 
# Driver code
arr = [1, 6, 3, 1, 3, 6, 6]
arr_size = len(arr)
 
print("The repeating elements are:")
 
# Function call
printRepeating(arr, arr_size)
 
# This code is contributed
# by Shreyanshi Arun.

// C# program to print all elements that
// appear more than once.
 
using System;
class GFG {
 
    // function to find repeating elements
    static void printRepeating(int[] arr, int n)
    {
        // First check all the values that are
        // present in an array then go to that
        // values as indexes and increment by
        // the size of array
        for (int i = 0; i < n; i++)
        {
            int index = arr[i] % n;
            arr[index] += n;
        }
 
        // Now check which value exists more
        // than once by dividing with the size
        // of array
        for (int i = 0; i < n; i++)
        {
            if ((arr[i] / n) >= 2)
                Console.Write(i + " ");
        }
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 6, 3, 1, 3, 6, 6 };
        int arr_size = arr.Length;
 
        Console.Write("The repeating elements are: "
                      + "\n");
 
        // Function call
        printRepeating(arr, arr_size);
    }
}

<?php
// PHP program to print all
// elements that appear more
// than once.
 
// function to find
// repeating elements
function printRepeating( $arr, $n)
{
    // First check all the values
    // that are present in an array
    // then go to that values as indexes
    // and increment by the size of array
    for ($i = 0; $i < $n; $i++)
    {
        $index = $arr[$i] % $n;
        $arr[$index] += $n;
    }
 
    // Now check which value
    // exists more than once
    // by dividing with the
    // size of array
    for ($i = 0; $i < $n; $i++)
    {
        if (($arr[$i] / $n) >= 2)
            echo $i , " ";
    }
}
 
// Driver code
$arr = array(1, 6, 3, 1, 3, 6, 6);
$arr_size = sizeof($arr) /
            sizeof($arr[0]);
 
echo "The repeating elements are: \n";
 
// Function call
printRepeating( $arr, $arr_size);
 
// This code is contributed by nitin mittal.
?>

<script>
 
// Javascript program to print all elements that
// appear more than once.   
     
    // function to find repeating elements
    function printRepeating(arr,n)
    {
        // First check all the values that are
        // present in an array then go to that
        // values as indexes and increment by
        // the size of array
        for (let i = 0; i < n; i++)
        {
            let index = arr[i] % n;
            arr[index] += n;
        }
  
        // Now check which value exists more
        // than once by dividing with the size
        // of array
        for (let i = 0; i < n; i++)
        {
            if ((arr[i] / n) >= 2)
                document.write(i + " ");
        }
    }
     
    // Driver code
    let arr=[1, 6, 3, 1, 3, 6, 6];
    let arr_size = arr.length;
    document.write("The repeating elements are: <br>");
     
    // Function call
    printRepeating(arr, arr_size);
     
    //  This code is contributed by avanitrachhadiya2155
     
</script>

The repeating elements are: 
1 3 6 

Análisis de complejidad : 

• Complejidad temporal: O(n).  
  Solo se necesitan dos recorridos. Entonces la complejidad del tiempo es O(n)
• Espacio Auxiliar: O(1). 
  Como no se necesita espacio adicional, la complejidad del espacio es constante

Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.