Dada una array de n elementos que contiene elementos de 0 a n-1, cualquiera de estos números aparece cualquier número de veces. Encuentre estos números repetidos en O (n) y use solo espacio de memoria constante. Se requiere que se mantenga el orden en que se repiten los elementos. Si no hay ningún elemento repetitivo presente, imprima -1.
Ejemplos:
Input : arr[] = {1, 2, 3, 1, 3, 6, 6}
Output : 1, 3, 6
Elements 1, 3 and 6 are repeating.
Second occurrence of 1 is found
first followed by repeated occurrence
of 3 and 6.
Input : arr[] = {0, 3, 1, 3, 0}
Output : 3, 0
Second occurrence of 3 is found
first followed by second occurrence
of 0.
Hemos discutido dos enfoques para esta pregunta en las publicaciones a continuación:
Buscar duplicados en tiempo O (n) y espacio extra O (1) | Establezca 1
duplicados en una array en tiempo O (n) y usando O (1) espacio adicional | Conjunto-2
Hay un problema en el primer acercamiento. Imprime el número repetido más de una vez. Por ejemplo: {1, 6, 3, 1, 3, 6, 6} dará como resultado: 3 6 6. En el segundo enfoque, aunque cada elemento repetido se imprime solo una vez, el orden en que ocurre su repetición no se mantiene . Para imprimir elementos en el orden en que se repiten, se modifica el segundo enfoque. Para marcar la presencia de un tamaño de elemento de la array, se agrega n a la posición de índice arr[i] correspondiente al elemento de la array arr[i]. Antes de agregar n, verifique si el valor en el índice arr[i] es mayor o igual que n o no. Si es mayor o igual que, significa que el elemento arr[i] se repite. Para evitar imprimir elementos repetidos varias veces, compruebe si es la primera repetición de arr[i] o no. Es la primera repetición si el valor en la posición de índice arr[i] es menor que 2*n. Esto se debe a que, si el elemento arr[i] se ha producido solo una vez antes, n se agrega al índice arr[i] solo una vez y, por lo tanto, el valor en el índice arr[i] es menor que 2*n. Agregue n al índice arr[i] para que el valor sea mayor o igual a 2*n y evitará más impresiones del elemento repetitivo actual. Además, si el valor en el índice arr[i] es menor que n, entonces es la primera aparición (no repetición) del elemento arr[i]. Entonces, para marcar esto, agregue n al elemento en el índice arr [i].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all elements that
// appear more than once.
#include <bits/stdc++.h>
using namespace std;
// Function to find repeating elements
void printDuplicates(int arr[], int n)
{
int i;
// Flag variable used to
// represent whether repeating
// element is found or not.
int fl = 0;
for (i = 0; i < n; i++) {
// Check if current element is
// repeating or not. If it is
// repeating then value will
// be greater than or equal to n.
if (arr[arr[i] % n] >= n) {
// Check if it is first
// repetition or not. If it is
// first repetition then value
// at index arr[i] is less than
// 2*n. Print arr[i] if it is
// first repetition.
if (arr[arr[i] % n] < 2 * n) {
cout << arr[i] % n << " ";
fl = 1;
}
}
// Add n to index arr[i] to mark
// presence of arr[i] or to
// mark repetition of arr[i].
arr[arr[i] % n] += n;
}
// If flag variable is not set
// then no repeating element is
// found. So print -1.
if (!fl)
cout << "-1";
}
// Driver Function
int main()
{
int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printDuplicates(arr, arr_size);
return 0;
}
Java
// Java program to print all elements
// that appear more than once.
import java.io.*;
class GFG
{
// Function to find repeating elements
static void printDuplicates(int arr[], int n)
{
int i;
// Flag variable used to
// represent whether repeating
// element is found or not.
int fl = 0;
for (i = 0; i < n; i++)
{
// Check if current element is
// repeating or not. If it is
// repeating then value will
// be greater than or equal to n.
if (arr[arr[i] % n] >= n)
{
// Check if it is first
// repetition or not. If it is
// first repetition then value
// at index arr[i] is less than
// 2*n. Print arr[i] if it is
// first repetition.
if (arr[arr[i] % n] < 2 * n)
{
System.out.print( arr[i] % n + " ");
fl = 1;
}
}
// Add n to index arr[i] to mark
// presence of arr[i] or to
// mark repetition of arr[i].
arr[arr[i] % n] += n;
}
// If flag variable is not set
// then no repeating element is
// found. So print -1.
if (!(fl > 0))
System.out.println("-1");
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
int arr_size = arr.length;
printDuplicates(arr, arr_size);
}
}
// This code is contributed by anuj_67.
Python 3
# Python 3 program to print all elements that
# appear more than once.
# Function to find repeating elements
def printDuplicates(arr, n):
# Flag variable used to
# represent whether repeating
# element is found or not.
fl = 0;
for i in range (0, n):
# Check if current element is
# repeating or not. If it is
# repeating then value will
# be greater than or equal to n.
if (arr[arr[i] % n] >= n):
# Check if it is first
# repetition or not. If it is
# first repetition then value
# at index arr[i] is less than
# 2*n. Print arr[i] if it is
# first repetition.
if (arr[arr[i] % n] < 2 * n):
print(arr[i] % n, end = " ")
fl = 1;
# Add n to index arr[i] to mark
# presence of arr[i] or to
# mark repetition of arr[i].
arr[arr[i] % n] += n;
# If flag variable is not set
# then no repeating element is
# found. So print -1.
if (fl == 0):
print("-1")
# Driver Function
arr = [ 1, 6, 3, 1, 3, 6, 6 ];
arr_size = len(arr);
printDuplicates(arr, arr_size);
# This code is contributed
# by Akanksha Rai
C#
// C# program to print all elements
// that appear more than once.
using System;
class GFG
{
// Function to find repeating elements
static void printDuplicates(int []arr, int n)
{
int i;
// Flag variable used to
// represent whether repeating
// element is found or not.
int fl = 0;
for (i = 0; i < n; i++)
{
// Check if current element is
// repeating or not. If it is
// repeating then value will
// be greater than or equal to n.
if (arr[arr[i] % n] >= n)
{
// Check if it is first
// repetition or not. If it is
// first repetition then value
// at index arr[i] is less than
// 2*n. Print arr[i] if it is
// first repetition.
if (arr[arr[i] % n] < 2 * n)
{
Console.Write( arr[i] % n + " ");
fl = 1;
}
}
// Add n to index arr[i] to mark
// presence of arr[i] or to
// mark repetition of arr[i].
arr[arr[i] % n] += n;
}
// If flag variable is not set
// then no repeating element is
// found. So print -1.
if (!(fl > 0))
Console.Write("-1");
}
// Driver Code
public static void Main ()
{
int []arr = { 1, 6, 3, 1, 3, 6, 6 };
int arr_size = arr.Length;
printDuplicates(arr, arr_size);
}
}
// This code is contributed
// by 29AjayKumar
PHP
<?php
// PHP program to print all elements that
// appear more than once.
// Function to find repeating elements
function printDuplicates($arr, $n)
{
$i;
// Flag variable used to
// represent whether repeating
// element is found or not.
$fl = 0;
for ($i = 0; $i < $n; $i++)
{
// Check if current element is
// repeating or not. If it is
// repeating then value will
// be greater than or equal to n.
if ($arr[$arr[$i] % $n] >= $n)
{
// Check if it is first
// repetition or not. If it is
// first repetition then value
// at index arr[i] is less than
// 2*n. Print arr[i] if it is
// first repetition.
if ($arr[$arr[$i] % $n] < 2 * $n)
{
echo $arr[$i] % $n . " ";
$fl = 1;
}
}
// Add n to index arr[i] to mark
// presence of arr[i] or to
// mark repetition of arr[i].
$arr[$arr[$i] % $n] += $n;
}
// If flag variable is not set
// then no repeating element is
// found. So print -1.
if (!$fl)
echo "-1";
}
// Driver Function
$arr = array(1, 6, 3, 1, 3, 6, 6);
$arr_size = sizeof($arr);
printDuplicates($arr, $arr_size);
// This code is contributed
// by Mukul Singh
Javascript
<script>
// JavaScript program to print all elements that
// appear more than once.
// Function to find repeating elements
function printDuplicates(arr, n)
{
let i;
// Flag variable used to
// represent whether repeating
// element is found or not.
let fl = 0;
for (i = 0; i < n; i++) {
// Check if current element is
// repeating or not. If it is
// repeating then value will
// be greater than or equal to n.
if (arr[arr[i] % n] >= n) {
// Check if it is first
// repetition or not. If it is
// first repetition then value
// at index arr[i] is less than
// 2*n. Print arr[i] if it is
// first repetition.
if (arr[arr[i] % n] < 2 * n) {
document.write(arr[i] % n + " ");
fl = 1;
}
}
// Add n to index arr[i] to mark
// presence of arr[i] or to
// mark repetition of arr[i].
arr[arr[i] % n] += n;
}
// If flag variable is not set
// then no repeating element is
// found. So print -1.
if (!fl)
document.write("-1");
}
// Driver Function
let arr = [ 1, 6, 3, 1, 3, 6, 6 ];
let arr_size = arr.length;
printDuplicates(arr, arr_size);
// This code is contributed by Surbhi Tyagi.
</script>
1 3 6
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.