Tutorialspoint.dev

Find top three repeated in array

Given an array of size N with repeated numbers, You Have to Find the top three repeated numbers.
Note : If Number comes same number of times then our output is one who comes first in array
Examples:

Input : arr[] = {3, 4, 2, 3, 16, 3, 15, 16, 15, 15, 16, 2, 3}
Output : Three largest elements are 3 16 15
Explanation :Here, 3 comes 4 times, 16 comes 3 times, 15 comes 3 times.

Input : arr[] = {2, 4, 3, 2, 3, 4, 5, 5, 3, 2, 2, 5}
Output : Three largest elements are 2 3 5

Asked in : Zoho

First We have to find the frequency of each element in a hash table freq. Now Our Task is to Find top 3 elements in the hash table, To Find it We just use three pair type variable ( suppose x, y, z)in which first store the frequency and second store the actual number.
Algorithm

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++ 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;
}

Output:

Three largest elements are 3 15 16

Time Complexity : O(n)
Auxiliary Space : O(n)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter