अ‍ॅरेमध्ये पुनरावृत्ती केलेले शीर्ष तीन शोधा


अडचण पातळी सोपे
वारंवार विचारले एमक्यू o9 सोल्यूशन्स विप्रो
अरे हॅश

“अ‍ॅरेमध्ये वारंवार शीर्ष तीन पुन्हा शोधा” ही समस्या सांगते की आपल्याला एक दिले गेले आहे अॅरे त्यामध्ये काही पुनरावृत्ती केलेल्या संख्येसह एन नंबरचे. अ‍ॅरेमध्ये शीर्ष 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 वारंवार घटक शोधा. तर, प्रत्येक घटकाची वारंवारता मोजणे आणि संग्रहित करणे ही आमची मुख्य कल्पना आहे. आम्ही नकाशा वापरुन हे करत आहोत. मग आणखी एक कल्पना येते की एक क्लास घोषित करणे आणि त्या वर्गाची ऑब्जेक्ट्स वापरण्यासाठी आमची व्हॅल्यूज तपासण्यासाठी आणि स्टोअर करणे.

आम्ही प्रत्येक घटकाची वारंवारता मोजू आणि नंतर आम्ही इतर तीन क्रमांकामध्ये मोठी संख्या शोधण्यासाठी वापरल्या जाणार्‍या नकाशामधील प्रत्येक इतर वारंवारतेशी तुलना करू.

चला त्याचं उदाहरण घेऊ आणि हे समजून घेऊ.

अरे [] = {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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. हॅशमॅप वापरल्यामुळे, आम्ही "अ‍ॅरेमध्ये शीर्षस्थानी पुन्हा शोधा" रेखीय समस्या निर्माण करण्याच्या महत्त्वपूर्ण कारणाने वेळेची जटिलता कमी करण्यास सक्षम होतो.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. सर्वात वाईट परिस्थितीत आम्ही एन की-व्हॅल्यू जोड्या संचयित करत आहोत. अशा प्रकारे अवकाशातील अवघडपणा देखील रेषात्मक आहे.