शीर्ष तीन बार सरणी में खोजें


कठिनाई स्तर आसान
में अक्सर पूछा MAQ ओ 9 के समाधान विप्रो
ऐरे हैश

समस्या "शीर्ष तीन बार सरणी में खोजें" बताता है कि आपको एक दिया गया है सरणी 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. घोषित करें नक्शा और उपयोगकर्ता परिभाषित वर्ग जिसे Pair कहा जाता है।
  2. यदि कम से कम तीन मान मौजूद नहीं हैं, तो वापस लौटें।
  3. इनपुट के प्रत्येक तत्व की आवृत्तियों को गिनें और संग्रहीत करें सरणी और इसे मानचित्र में डालें।
  4. जोड़ी वर्ग की वस्तुओं को बनाएं और इसे एक पूर्णांक के न्यूनतम मूल्य के साथ प्रारंभ करें।
  5. जबकि नक्शे को ट्रेस किया जा रहा है।
    1. जांचें कि वर्तमान कुंजी की आवृत्ति असाइन की गई वस्तुओं से अधिक है या नहीं।
    2. यदि सही है, तो सभी कुंजी और मान को Pair की अन्य वस्तुओं में स्थानांतरित करें।
  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 दोहराए गए तत्वों को प्रिंट करते हैं।

कोड

C ++ कोड सरणी में दोहराए गए शीर्ष तीन को खोजने के लिए

#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

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। हशमप का उपयोग करने के कारण, हम एक महत्वपूर्ण कारक "सरणी में दोहराए गए शीर्ष तीन को दोहराएं" को बनाते हुए समय की जटिलता को कम करने में सक्षम थे।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। सबसे खराब स्थिति में, हम n कुंजी-मूल्य जोड़े का भंडारण करेंगे। इस प्रकार अंतरिक्ष की जटिलता भी रैखिक है।