Encuentre duplicados en una array constante con elementos 0 a N-1 en el espacio O (1)

Posted on by Rudeus Greyrat

Dada una array constante de n elementos que contiene elementos de 1 a n-1, cualquiera de estos números aparece cualquier número de veces. Encuentre cualquiera de estos números repetidos en O (n) y use solo espacio de memoria constante.
Ejemplos: 
 

Input : arr[] = {1, 2, 3, 4, 5, 6, 3}
Output : 3

Como la array dada es constante, los métodos dados en los siguientes artículos no funcionarán. 
 

  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
  1. Estamos tomando dos variables i & j comenzando desde 0
  2. Ejecutaremos el ciclo hasta que llegue al último elemento o encuentre elementos repetidos
  3. Incrementaremos previamente el valor de j para que podamos comparar el elemento con el elemento siguiente
  4. Si no encontramos el elemento, aumentaremos i ya que j apuntará al último elemento y luego reposicionaremos j con i
     

Java

// Java program to find a duplicate
// element in an array with values in
// range from 0 to n-1.
import java.io.*;
import java.util.*;
 
public class GFG {
     
    // function to find one duplicate
    static int findduplicate(int []a, int n)
    {
         
        int i=0,j=0;
        while(i<n){
            if(a[i]==a[++j]) return a[j];
            if(j==n-1) {
                i++;
                j=i;
            }
        }
        return -1;
    }
     
    public static void main(String args[])
    {
        int []arr = {1, 2, 4, 3, 4, 5, 6, 3};
        int n = arr.length;
        System.out.print(findduplicate(arr, n));
    }
}
 
// This code is contributed by
// Love Raj

Java

// Java program to find a duplicate
// element in an array with values in
// range from 0 to n-1.
import java.io.*;
import java.util.*;
 
public class GFG {
      
    // function to find one duplicate
    static int findduplicate(int []arr, int n)
    {
          
        // return -1 because in these cases
        // there can not be any repeated element
        if (n <= 1)
            return -1;
      
        // initialize fast and slow
        int slow = arr[0];
        int fast = arr[arr[0]];
      
        // loop to enter in the cycle
        while (fast != slow)
        {
      
            // move one step for slow
            slow = arr[slow];
      
            // move two step for fast
            fast = arr[arr[fast]];
        }
      
        // loop to find entry
        // point of the cycle
        fast = 0;
        while (slow != fast)
        {
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
      
    // Driver Code
    public static void main(String args[])
    {
        int []arr = {1, 2, 3, 4, 5, 6, 3};
        int n = arr.length;
        System.out.print(findduplicate(arr, n));
    }
}
  
// This code is contributed by
// Manish Shaw (manishshaw1)

Python 3

# Python 3 program to find a duplicate
# element in an array with values in
# range from 0 to n-1.
 
# function to find one duplicate
def findduplicate(arr, n):
 
    # return -1 because in these cases
    # there can not be any repeated element
    if (n <= 1):
        return -1
 
    # initialize fast and slow
    slow = arr[0]
    fast = arr[arr[0]]
 
    # loop to enter in the cycle
    while (fast != slow) :
 
        # move one step for slow
        slow = arr[slow]
 
        # move two step for fast
        fast = arr[arr[fast]]
 
    # loop to find entry point of the cycle
    fast = 0
    while (slow != fast):
        slow = arr[slow]
        fast = arr[fast]
    return slow
 
# Driver Code
if __name__ == "__main__":
     
    arr = [1, 2, 3, 4, 5, 6, 3 ]
    n = len(arr)
    print(findduplicate(arr, n))
 
# This code is contributed by ita_c

C#

// C# program to find a duplicate
// element in an array with values in
// range from 0 to n-1.
using System;
using System.Collections.Generic;
class GFG {
     
    // function to find one duplicate
    static int findduplicate(int []arr, int n)
    {
         
        // return -1 because in these cases
        // there can not be any repeated element
        if (n <= 1)
            return -1;
     
        // initialize fast and slow
        int slow = arr[0];
        int fast = arr[arr[0]];
     
        // loop to enter in the cycle
        while (fast != slow)
        {
     
            // move one step for slow
            slow = arr[slow];
     
            // move two step for fast
            fast = arr[arr[fast]];
        }
     
        // loop to find entry
        // point of the cycle
        fast = 0;
        while (slow != fast)
        {
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = {1, 2, 3, 4, 5, 6, 3};
        int n = arr.Length;
        Console.Write(findduplicate(arr, n));
    }
}
 
// This code is contributed by
// Manish Shaw (manishshaw1)

PHP

<?php
// PHP program to find a duplicate
// element in an array with values in
// range from 0 to n-1.
 
// function to find one duplicate
function findduplicate($arr, $n)
{
    // return -1 because in these cases
    // there can not be any repeated element
    if ($n <= 1)
        return -1;
 
    // initialize fast and slow
    $slow = $arr[0];
    $fast = $arr[$arr[0]];
 
    // loop to enter in the cycle
    while ($fast != $slow)
    {
 
        // move one step for slow
        $slow = $arr[$slow];
 
        // move two step for fast
        $fast = $arr[$arr[$fast]];
    }
 
    // loop to find entry point of the cycle
    $fast = 0;
    while ($slow != $fast)
    {
        $slow = $arr[$slow];
        $fast = $arr[$fast];
    }
    return $slow;
}
 
// Driver Code
$arr = array( 1, 2, 3, 4, 5, 6, 3 );
$n = sizeof($arr);
echo findduplicate($arr, $n);
 
// This code is contributed by Tushil
?>

Javascript

<script>
 
    // Javascript program to find a duplicate
    // element in an array with values in
    // range from 0 to n-1.
     
    // function to find one duplicate
    function findduplicate(arr, n)
    {
           
        // return -1 because in these cases
        // there can not be any repeated element
        if (n <= 1)
            return -1;
       
        // initialize fast and slow
        let slow = arr[0];
        let fast = arr[arr[0]];
       
        // loop to enter in the cycle
        while (fast != slow)
        {
       
            // move one step for slow
            slow = arr[slow];
       
            // move two step for fast
            fast = arr[arr[fast]];
        }
       
        // loop to find entry
        // point of the cycle
        fast = 0;
        while (slow != fast)
        {
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
     
    let arr = [1, 2, 3, 4, 5, 6, 3];
    let n = arr.length;
    document.write(findduplicate(arr, n));
     
</script>

Producción:  

3

Complejidad temporal: O(n*n) 
Espacio auxiliar: O(1)

Enfoque eficiente:

Usaremos el concepto de que todos los elementos aquí están entre 1 y n-1.

Así que realizaremos estos pasos para encontrar el elemento Duplicado

  1.  Considere un puntero ‘p’ que se encuentra actualmente en el índice 0.
  2.  Ejecute un bucle while hasta que el puntero p alcance el valor n.
  3.  si el valor de a[p] es -1, incremente el puntero en 1 y omita la iteración 
  4.  De lo contrario, vaya a la posición del elemento al que apunta el puntero actual, es decir, al índice a[p].
  5.  Ahora, si el valor en el índice a[p], es decir, a[a[p]] es -1, rompa el bucle ya que el elemento a[p] es el duplicado.
  6. De lo contrario, almacene el valor de a[a[p]] en a[p], es decir, a[p]=a[a[p]] y coloque -1 en a[a[p]], es decir, a[a[p]] =-1.

Código:

       

C++

#include <iostream>
using namespace std;
 
void find_duplicate(int a[], int n)
{
    int p = 0;
    while (p != n) {
        if (a[p] == -1) {
            p++;
        }
        else {
            if (a[a[p] - 1] == -1) {
                cout << a[p] << endl;
                break;
            }
            else {
                a[p] = a[a[p] - 1];
                a[a[p] - 1] = -1;
            }
        }
    }
}
 
int main()
{
    int a[] = { 1, 2, 4, 3, 4, 5, 6, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    find_duplicate(a, n);
    return 0;
}
 
// This Code is Contributed by Abhishek Purohit

Java

// Java Program for the above approach
 
import java.io.*;
 
class GFG {
 
    static void find_duplicate(int a[], int n)
    {
        int p = 0;
        while (p != n) {
            if (a[p] == -1) {
                p++;
            }
            else {
                if (a[a[p] - 1] == -1) {
                    System.out.println(a[p]);
                    break;
                }
                else {
                    a[p] = a[a[p] - 1];
                    a[a[p] - 1] = -1;
                }
            }
        }
    }
 
    public static void main(String[] args)
    {
        int[] a = { 1, 2, 4, 3, 4, 5, 6, 3 };
        int n = a.length;
 
        find_duplicate(a, n);
    }
}
 
// This Code is Contributed by lokesh (lokeshmvs21).
Producción

3

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por niteesh_Kr 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 *