Dada una array de tamaño N con números repetidos, debe encontrar los tres primeros números repetidos.
Nota: si el número aparece el mismo número de veces, nuestra salida es la que aparece primero en la array
. Ejemplos:
Entrada: arr[] = {3, 4, 2, 3, 16, 3, 15, 16, 15, 15, 16, 2, 3}
Salida: Los tres elementos más grandes son 3 16 15
Explicación: Aquí, 3 viene 4 veces , 16 viene 3 veces, 15 viene 3 veces.
Entrada: arr[] = {2, 4, 3, 2, 3, 4, 5, 5, 3, 2, 2, 5}
Salida: Los tres elementos más grandes son 2 3 5
Preguntado en : Zoho
Primero Tenemos que encontrar la frecuencia de cada elemento en una tabla hash freq . Ahora nuestra tarea es encontrar los 3 elementos principales en la tabla hash. Para encontrarlo, solo usamos tres variables de tipo par (supongamos que x, y, z) en las que primero almacenamos la frecuencia y segundo almacenamos el número real.
Algoritmo
1) Initialize the largest three elements
as Minimum value.
x.first = y.first = z.first = Minus-Infinite
2) Iterate through all elements of the
hash table freq.
a) Let current array element be p.
b) If (fre[p] !=0 && fre[p] > x.first)
{
// This order of assignment is important
z = y
y = x
x.first = fre[p]
x.second = p;
}
c) Else if (fre[p] !=0 && free[p] > y.first)
{
z = y
y.first = fre[p]
y.second = p
}
d) Else if (fre[p] !=0 && free[p] > z.first)
{
z.first = fre[p]
z.second = p
}
// Modify frequency of Current element
// as zero because We Traverse Initial
// array arr[]. So it don't take same
// values again
3) fre[p] = 0
3) Print x.second, y.second and z.second.
C++
// C++ Program to Find the top three repeated numbers
#include <bits/stdc++.h>
using namespace std;
/* Function to print top three repeated numbers */
void top3Repeated(int arr[], int n)
{
// There should be atleast two elements
if (n < 3) {
cout << "Invalid Input";
return;
}
// Count Frequency of each element
unordered_map<int, int> fre;
for (int i = 0; i < n; i++)
fre[arr[i]]++;
// Initialize first value of each variable
// of Pair type is INT_MIN
pair<int, int> x, y, z;
x.first = y.first = z.first = INT_MIN;
for (auto curr : fre) {
// If frequency of current element
// is not zero and greater than
// frequency of first largest element
if (curr.second > x.first) {
// Update second and third largest
z = y;
y = x;
// Modify values of x Number
x.first = curr.second;
x.second = curr.first;
}
// If frequency of current element is
// not zero and frequency of current
// element is less than frequency of
// first largest element, but greater
// than y element
else if (curr.second > y.first) {
// Modify values of third largest
z = y;
// Modify values of second largest
y.first = curr.second;
y.second = curr.first;
}
// If frequency of current element
// is not zero and frequency of
// current element is less than
// frequency of first element and
// second largest, but greater than
// third largest.
else if (curr.second > z.first) {
// Modify values of z Number
z.first = curr.second;
z.second = curr.first;
}
}
cout << "Three largest elements are " << x.second << " "
<< y.second << " " << z.second;
}
// Driver's Code
int main()
{
int arr[]
= { 3, 4, 2, 3, 16, 3, 15, 16, 15, 15, 16, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
top3Repeated(arr, n);
return 0;
}
Java
// Java Program to Find the top three repeated numbers
import java.io.*;
import java.util.*;
// User defined Pair class
class Pair {
int first, second;
}
class GFG {
// Function to print top three repeated numbers
static void top3Repeated(int[] arr, int n)
{
// There should be atleast two elements
if (n < 3) {
System.out.print("Invalid Input");
return;
}
// Count Frequency of each element
TreeMap<Integer, Integer> freq = new TreeMap<>();
for (int i = 0; i < n; i++)
if (freq.containsKey(arr[i]))
freq.put(arr[i], 1 + freq.get(arr[i]));
else
freq.put(arr[i], 1);
// Initialize first value of each variable
// of Pair type is INT_MIN
Pair x = new Pair();
Pair y = new Pair();
Pair z = new Pair();
x.first = y.first = z.first = Integer.MIN_VALUE;
for (Map.Entry curr : freq.entrySet()) {
// If frequency of current element
// is not zero and greater than
// frequency of first largest element
if (Integer.parseInt(String.valueOf(curr.getValue())) > x.first) {
// Update second and third largest
z.first = y.first;
z.second = y.second;
y.first = x.first;
y.second = x.second;
// Modify values of x Number
x.first = Integer.parseInt(String.valueOf(curr.getValue()));
x.second = Integer.parseInt(String.valueOf(curr.getKey()));
}
// If frequency of current element is
// not zero and frequency of current
// element is less than frequency of
// first largest element, but greater
// than y element
else if (Integer.parseInt(String.valueOf(curr.getValue())) > y.first) {
// Modify values of third largest
z.first = y.first;
z.second = y.second;
// Modify values of second largest
y.first = Integer.parseInt(String.valueOf(curr.getValue()));
y.second = Integer.parseInt(String.valueOf(curr.getKey()));
}
// If frequency of current element
// is not zero and frequency of
// current element is less than
// frequency of first element and
// second largest, but greater than
// third largest.
else if (Integer.parseInt(String.valueOf(curr.getValue())) > z.first) {
// Modify values of z Number
z.first = Integer.parseInt(String.valueOf(curr.getValue()));
z.second = Integer.parseInt(String.valueOf(curr.getKey()));
}
}
System.out.print("Three largest elements are " + x.second + " "
+ y.second + " " + z.second);
}
// Driver's Code
public static void main(String args[])
{
int[] arr = { 3, 4, 2, 3, 16, 3, 15,
16, 15, 15, 16, 2, 3 };
int n = arr.length;
top3Repeated(arr, n);
}
}
// This code is contributed by rachana soma
Python3
# Python Program to Find the top three repeated numbers
# User defined Pair class
import sys
class Pair:
def __init__(self,first = 0,second = 0):
self.first = first
self.second = second
# Function to print top three repeated numbers
def top3Repeated(arr, n):
# There should be atleast two elements
if (n < 3):
print("Invalid Input")
return
# Count Frequency of each element
arr.sort()
freq = {}
for i in range(n):
if (arr[i] in freq):
freq[arr[i]] = 1 + freq[arr[i]]
else:
freq[arr[i]] = 1
# Initialize first value of each variable
# of Pair type is INT_MIN
x = Pair()
y = Pair()
z = Pair()
x.first = y.first = z.first = -sys.maxsize -1
for curr,curr2 in freq.items():
# If frequency of current element
# is not zero and greater than
# frequency of first largest element
if (int(curr2) > x.first):
# Update second and third largest
z.first = y.first
z.second = y.second
y.first = x.first
y.second = x.second
# Modify values of x Number
x.first = int((curr2))
x.second = int((curr))
# If frequency of current element is
# not zero and frequency of current
# element is less than frequency of
# first largest element, but greater
# than y element
elif (int((curr2)) > y.first):
# Modify values of third largest
z.first = y.first
z.second = y.second
# Modify values of second largest
y.first = int((curr2))
y.second = int((curr))
# If frequency of current element
# is not zero and frequency of
# current element is less than
# frequency of first element and
# second largest, but greater than
# third largest.
elif (int((curr2)) > z.first):
# Modify values of z Number
z.first = int((curr2))
z.second = int((curr))
print(f"Three largest elements are {x.second} {y.second} {z.second}")
# Driver's Code
arr = [ 3, 4, 2, 3, 16, 3, 15, 16, 15, 15, 16, 2, 3 ]
n = len(arr)
top3Repeated(arr, n)
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript Program to Find the top three repeated numbers
// User defined Pair class
class Pair {
constructor(first, second){
this.first = first;
this.second = second;
}
}
// Function to print top three repeated numbers
function top3Repeated(arr, n)
{
// There should be atleast two elements
if (n < 3) {
document.write("Invalid Input");
return;
}
// Count Frequency of each element
arr.sort((a, b) => a - b)
let freq = new Map();
for (let i = 0; i < n; i++)
if (freq.has(arr[i]))
freq.set(arr[i], 1 + freq.get(arr[i]));
else
freq.set(arr[i], 1);
// Initialize first value of each variable
// of Pair type is INT_MIN
let x = new Pair();
let y = new Pair();
let z = new Pair();
x.first = y.first = z.first = Number.MIN_SAFE_INTEGER;
for (let curr of freq) {
// If frequency of current element
// is not zero and greater than
// frequency of first largest element
if (parseInt(curr[1]) > x.first) {
// Update second and third largest
z.first = y.first;
z.second = y.second;
y.first = x.first;
y.second = x.second;
// Modify values of x Number
x.first = parseInt((curr[1]));
x.second = parseInt((curr[0]));
}
// If frequency of current element is
// not zero and frequency of current
// element is less than frequency of
// first largest element, but greater
// than y element
else if (parseInt((curr[1])) > y.first) {
// Modify values of third largest
z.first = y.first;
z.second = y.second;
// Modify values of second largest
y.first = parseInt((curr[1]));
y.second = parseInt((curr[0]));
}
// If frequency of current element
// is not zero and frequency of
// current element is less than
// frequency of first element and
// second largest, but greater than
// third largest.
else if (parseInt((curr[1])) > z.first) {
// Modify values of z Number
z.first = parseInt((curr[1]));
z.second = parseInt((curr[0]));
}
}
document.write("Three largest elements are " + x.second + " "
+ y.second + " " + z.second);
}
// Driver's Code
let arr = [ 3, 4, 2, 3, 16, 3, 15,
16, 15, 15, 16, 2, 3 ];
let n = arr.length;
top3Repeated(arr, n);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
Three largest elements are 3 15 16
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)