ശ്രേണിയിൽ ആവർത്തിച്ചുള്ള ആദ്യ മൂന്ന് കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു MAQ o9 പരിഹാരങ്ങൾ വിപ്രോ
അറേ ഹാഷ്

“നിരയിൽ ആവർത്തിച്ചുള്ള ആദ്യ മൂന്ന് കണ്ടെത്തുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി ആവർത്തിച്ചുള്ള ചില സംഖ്യകളുള്ള n സംഖ്യകളുടെ. ഒരു അറേയിലെ ആവർത്തിച്ചുള്ള മികച്ച 3 നമ്പറുകൾ കണ്ടെത്തുക എന്നതാണ് നിങ്ങളുടെ ചുമതല.

ഉദാഹരണം

ശ്രേണിയിൽ ആവർത്തിച്ചുള്ള ആദ്യ മൂന്ന് കണ്ടെത്തുക

[1,3,4,6,7,2,1,6,3,10,5,7]
1 3 6

വിശദീകരണം

ഇവിടെ 1,3 ഉം 6 ഉം രണ്ടുതവണ ആവർത്തിക്കുന്നു.

[2,4,2,1,5,6,8,5,3,9,0,1]
1 2 5

വിശദീകരണം

ഇവിടെ 1,2 ഉം 5 ഉം രണ്ടുതവണ ആവർത്തിക്കുന്നു.

ആവർത്തിച്ചുള്ള മൂന്ന് മികച്ച ഘടകങ്ങൾ കണ്ടെത്താനുള്ള അൽഗോരിതം

  1. പ്രഖ്യാപിക്കുക ഭൂപടം ഒപ്പം പെയർ എന്ന് വിളിക്കുന്ന ഉപയോക്തൃ നിർവചിത ക്ലാസും.
  2. കുറഞ്ഞത് മൂന്ന് മൂല്യങ്ങളെങ്കിലും ഇല്ലെങ്കിൽ മടങ്ങുക.
  3. ഇൻപുട്ടിന്റെ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തികൾ കണക്കാക്കി സംഭരിക്കുക ശ്രേണി എന്നിട്ട് മാപ്പിൽ ഇടുക.
  4. ജോഡി ക്ലാസിന്റെ ഒബ്‌ജക്റ്റുകൾ സൃഷ്‌ടിച്ച് ഒരു സംഖ്യയുടെ ഏറ്റവും കുറഞ്ഞ മൂല്യം ഉപയോഗിച്ച് ആരംഭിക്കുക.
  5. മാപ്പ് സഞ്ചരിക്കുമ്പോൾ.
    1. നിലവിലെ കീയുടെ ആവൃത്തി നിയുക്തമാക്കിയ ഒബ്‌ജക്റ്റുകളെക്കാൾ വലുതാണോയെന്ന് പരിശോധിക്കുക.
    2. ശരിയാണെങ്കിൽ, എല്ലാ കീകളും മൂല്യങ്ങളും ജോഡിയുടെ മറ്റ് ഒബ്‌ജക്റ്റുകളിലേക്ക് മാറ്റുക.
  6. മികച്ച മൂന്ന് ഘടകങ്ങൾ അച്ചടിക്കുക.

വിശദീകരണം

ചില സംഖ്യകളുള്ള ഒരു അറേ ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. ആവർത്തിച്ചുള്ള മികച്ച 3 ഘടകങ്ങൾ കണ്ടെത്തുക എന്നതാണ് പ്രശ്നം. അതിനാൽ, ഓരോ മൂലകത്തിന്റെയും ആവൃത്തികൾ കണക്കാക്കി സംഭരിക്കുക എന്നതാണ് ഞങ്ങളുടെ പ്രധാന ആശയം. ഒരു മാപ്പ് ഉപയോഗിച്ചാണ് ഞങ്ങൾ ഇത് ചെയ്യുന്നത്. മറ്റൊരു ആശയം വരുന്നു, അത് ഒരു ക്ലാസ് പ്രഖ്യാപിക്കുകയും ആ ക്ലാസിലെ ഒബ്‌ജക്റ്റുകൾ ഉപയോഗിച്ച് ഞങ്ങളുടെ മൂല്യങ്ങൾ പരിശോധിക്കാനും സംഭരിക്കാനും കഴിയും, അത് ഞങ്ങളുടെ .ട്ട്‌പുട്ട് ആകാം.

ഞങ്ങൾ ഓരോ ഘടക ആവൃത്തിയും പിന്നീട് മാപ്പിലെ മറ്റെല്ലാ ആവൃത്തികളുമായി താരതമ്യപ്പെടുത്താൻ പോകുന്നു, ഇത് മറ്റ് മൂന്ന് സംഖ്യകളിലെ വലിയ എണ്ണം കണ്ടെത്താൻ ഞങ്ങൾ ഉപയോഗിച്ചതുപോലുള്ള ഒരു വലിയ സംഖ്യയാണ്.

നമുക്ക് ഒരു ഉദാഹരണം പരിഗണിച്ച് ഇത് മനസ്സിലാക്കാം.

arr [] = {9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9}

അറേയിലെ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തികൾ കണക്കാക്കുന്നത് ആരംഭിക്കുന്നു. എല്ലാ ഘടകങ്ങളും അവയുടെ ആവൃത്തികളും സംഭരിച്ചിരിക്കുന്ന ഒരു മാപ്പ് നിർമ്മിക്കുന്നത് ഞങ്ങൾ അവസാനിപ്പിക്കും. ഞങ്ങളുടെ മാപ്പിൽ ഇനിപ്പറയുന്ന മൂല്യങ്ങൾ അടങ്ങിയിരിക്കും:

Freq= {1:3, 2:2, 4:1, 9:4,15:3,9:4}

ഞങ്ങൾക്ക് വേണ്ടതെല്ലാം ഉണ്ട്, ഇതിലെല്ലാം ആവർത്തിച്ചുള്ള മികച്ച 3 നമ്പറുകൾ കണ്ടെത്തേണ്ടതുണ്ട്. അതിനായി, സംഖ്യയുടെ ഏറ്റവും കുറഞ്ഞ മൂല്യമുള്ള ജോഡി ക്ലാസിലെ ഒബ്‌ജക്റ്റുകളുടെ മൂല്യം ഞങ്ങൾ സമാരംഭിക്കുന്നു. ഓരോ കീകളും അവയുടെ ആവൃത്തിയും ഞങ്ങൾ സഞ്ചരിക്കും. തുടർന്ന് x.first, y.first, z.first എന്നിങ്ങനെ ഒബ്‌ജക്റ്റുകളുമായി താരതമ്യം ചെയ്യുക. അവസാനം, ഒരു ശ്രേണിയിലെ ആവർത്തിച്ചുള്ള മികച്ച 3 ഘടകങ്ങൾ ഞങ്ങൾ അച്ചടിക്കുന്നു.

കോഡ്

അറേയിൽ ആവർത്തിച്ചുള്ള ആദ്യ മൂന്ന് കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#include <bits/stdc++.h>
using namespace std;
void getRepeatedNumbers(int arr[], int n)
{
    if (n < 3)
    {
        cout << "INVALID !! PLEASE ENTER CORRECT INPUT";
        return;
    }
    unordered_map<int, int> fre;
    for (int i = 0; i < n; i++)
        fre[arr[i]]++;

    pair<int, int> x, y, z;
    x.first = y.first = z.first = INT_MIN;

    for (auto val : fre)
    {
        if (val.second > x.first)
        {
            z = y;
            y = x;

            x.first = val.second;
            x.second = val.first;
        }
        else if (val.second > y.first)
        {
            z = y;

            y.first = val.second;
            y.second = val.first;
        }
        else if (val.second > z.first)
        {
            z.first = val.second;
            z.second = val.first;
        }
    }
    cout << "Top three repeated elements are  "<< x.second << " " << y.second<< " " << z.second;
}
int main()
{
    int arr[] = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getRepeatedNumbers(arr, n);
    return 0;
}
Top three repeated elements are  9 15 1

അറേയിൽ ആവർത്തിച്ചുള്ള ആദ്യ മൂന്ന് കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.io.*;
import java.util.*;

class Pair
{
    int first, second;
}
class topThreeRepeatedNumber
{
    public static void getRepeatedNumbers(int[] arr, int n)
    {
        if (n < 3)
        {
            System.out.print("INVALID !! PLEASE ENTER CORRECT INPUT");
            return;
        }
        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);
        }

        Pair x = new Pair();
        Pair y = new Pair();
        Pair z = new Pair();
        x.first = y.first = z.first = Integer.MIN_VALUE;

        for (Map.Entry val : freq.entrySet())
        {
            if (Integer.parseInt(String.valueOf(val.getValue())) > x.first)
            {

                z.first = y.first;
                z.second = y.second;
                y.first = x.first;
                y.second = x.second;

                x.first = Integer.parseInt(String.valueOf(val.getValue()));
                x.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > y.first)
            {
                z.first = y.first;
                z.second = y.second;

                y.first = Integer.parseInt(String.valueOf(val.getValue()));
                y.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > z.first)
            {
                z.first = Integer.parseInt(String.valueOf(val.getValue()));
                z.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
        }

        System.out.println("Top three repeated elements are " + x.second + ", "+ y.second + ", " + z.second);
    }
    public static void main(String args[])
    {
        int[] arr = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
        int n = arr.length;
        getRepeatedNumbers(arr, n);
    }
}
Top three repeated elements are 9, 1, 15

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുന്നതിനാൽ, “അറേയിൽ ആവർത്തിച്ചുള്ള മികച്ച മൂന്ന് പേരെ കണ്ടെത്തുക” എന്ന പ്രശ്‌നമുണ്ടാക്കുന്ന ഒരു പ്രധാന ഘടകത്തിലൂടെ സമയ സങ്കീർണ്ണത കുറയ്‌ക്കാൻ ഞങ്ങൾക്ക് കഴിഞ്ഞു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഏറ്റവും മോശം അവസ്ഥയിൽ, ഞങ്ങൾ n കീ-മൂല്യ ജോഡികൾ സംഭരിക്കും. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.