Encuentra los tres primeros repetidos en la array

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)
 

Publicación traducida automáticamente

Artículo escrito por Mr.Gera 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 *