Dada una array de enteros, imprima todos los elementos repetidos (elementos que aparecen más de una vez) en la array. La salida debe contener elementos según sus primeras apariciones.
Ejemplos:
Input: arr[] = {12, 10, 9, 45, 2, 10, 10, 45}
Output: 10 45
Input: arr[] = {1, 2, 3, 4, 2, 5}
Output: 2
Input: arr[] = {1, 1, 1, 1, 1}
Output: 1
La idea es usar Hashing para resolver esto en tiempo O(n) en promedio. Almacenamos elementos y sus recuentos en una tabla hash. Después de almacenar los conteos, recorremos la array de entrada nuevamente e imprimimos aquellos elementos cuyos conteos son más de una vez. Para asegurarnos de que cada elemento de salida se imprima solo una vez, configuramos el conteo como 0 después de imprimir el elemento.
C++
// C++ program to print all repeating elements
#include <bits/stdc++.h>
using namespace std;
void printRepeating(int arr[], int n)
{
// Store elements and their counts in
// hash table
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
// Since we want elements in same order,
// we traverse array again and print
// those elements that appear more than
// once.
for (int i = 0; i < n; i++) {
if (mp[arr[i]] > 1) {
cout << arr[i] << " ";
// This is tricky, this is done
// to make sure that the current
// element is not printed again
mp[arr[i]] = 0;
}
}
}
// Driver code
int main()
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = sizeof(arr) / sizeof(arr[0]);
printRepeating(arr, n);
return 0;
}
Java
// Java program to print all repeating elements
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.lang.*;
public class GFG {
static void printRepeating(int arr[], int n)
{
// Store elements and their counts in
// hash table
Map<Integer, Integer> map
= new LinkedHashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
try {
map.put(arr[i], map.get(arr[i]) + 1);
}
catch (Exception e) {
map.put(arr[i], 1);
}
}
// Since we want elements in the same order,
// we traverse array again and print
// those elements that appear more than once.
for (Entry<Integer, Integer> e : map.entrySet()) {
if (e.getValue() > 1) {
System.out.print(e.getKey() + " ");
}
}
}
// Driver code
public static void main(String[] args) throws IOException
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = arr.length;
printRepeating(arr, n);
}
}
// This code is contributed by Wrick
Python3
# Python3 program to print # all repeating elements def printRepeating(arr, n): # Store elements and # their counts in # hash table mp = [0] * 100 for i in range(0, n): mp[arr[i]] += 1 # Since we want elements # in same order, we # traverse array again # and print those elements # that appear more than once. for i in range(0, n): if (mp[arr[i]] > 1): print(arr[i], end = " ") # This is tricky, this # is done to make sure # that the current element # is not printed again mp[arr[i]] = 0 # Driver code arr = [12, 10, 9, 45, 2, 10, 10, 45] n = len(arr) printRepeating(arr, n) # This code is contributed # by Smita
C#
// C# program to print all repeating elements
using System;
using System.Collections.Generic;
class GFG
{
static void printRepeating(int []arr, int n)
{
// Store elements and their counts in
// hash table
Dictionary<int,
int> map = new Dictionary<int,
int>();
for (int i = 0 ; i < n; i++)
{
if(map.ContainsKey(arr[i]))
{
var val = map[arr[i]];
map.Remove(arr[i]);
map.Add(arr[i], val + 1);
}
else
{
map.Add(arr[i], 1);
}
}
// Since we want elements in the same order,
// we traverse array again and print
// those elements that appear more than once.
foreach(KeyValuePair<int, int> e in map)
{
if (e.Value > 1)
{
Console.Write(e.Key + " ");
}
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = arr.Length;
printRepeating(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to print all
// repeating elements
function printRepeating(arr, n)
{
// Store elements and their counts in
// hash table
var mp = new Map();
for (var i = 0; i < n; i++)
{
if(mp.has(arr[i]))
mp.set(arr[i], mp.get(arr[i])+1)
else
mp.set(arr[i], 1)
}
// Since we want elements in same order,
// we traverse array again and print
// those elements that appear more than
// once.
for (var i = 0; i < n; i++) {
if (mp.get(arr[i]) > 1) {
document.write( arr[i] + " ");
// This is tricky, this is done
// to make sure that the current
// element is not printed again
mp.set(arr[i], 0);
}
}
}
// Driver code
var arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ];
var n = arr.length;
printRepeating(arr, n);
</script>
Producción:
10 45
Complejidad de tiempo: O(n) bajo el supuesto de que las funciones de inserción y búsqueda de hash funcionan en tiempo O(1).
Espacio auxiliar: O(n), donde n representa el tamaño de la array dada.
Método n.º 2: uso de las funciones integradas de Python:
- Cuente todas las frecuencias de todos los elementos usando la función Counter() .
- Recorra este diccionario de frecuencias e imprima todas las claves cuyo valor sea mayor que 1.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 program to print # all repeating elements from collections import Counter def printRepeating(arr, n): # Counting frequencies freq = Counter(arr) # Traverse the freq dictionary and # print all the keys whose value # is greater than 1 for i in freq: if(freq[i] > 1): print(i, end=" ") # Driver code arr = [12, 10, 9, 45, 2, 10, 10, 45] n = len(arr) printRepeating(arr, n) # This code is contributed by vikkycirus
Producción:
10 45
Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(n), donde n representa el tamaño de la array dada.