दो तत्वों की आवृत्ति के बीच अधिकतम अंतर जैसे कि अधिक आवृत्ति वाले तत्व भी अधिक होते हैं


कठिनाई स्तर मध्यम
में अक्सर पूछा एक्सेंचर एकोलाइट वीरांगना VMware
ऐरे हैश छंटाई

मान लीजिए, आपके पास एक पूर्णांक है सरणी। समस्या कथन किसी दिए गए सरणी के किसी भी दो अलग-अलग तत्वों की आवृत्ति के बीच अधिकतम अंतर का पता लगाने के लिए कहता है, लेकिन अधिक आवृत्ति के साथ तत्व भी अन्य पूर्णांक की तुलना में अधिक होना चाहिए।

उदाहरण

इनपुट:

arr [] = {2,4,4,4,3,2}

आउटपुट:

2

स्पष्टीकरण:

4 → 3 की आवृत्ति

2 → 2 की आवृत्ति

और 3 → 1 की आवृत्ति

4 (3) - 3 (1) = 2 (पूर्णांक भी अधिक से अधिक और अधिकतम आवृत्ति हैं)।

कलन विधि

  1. डिक्लेयर ए नक्शा और एक सरणी लंबाई n की 'दूरी' कहती है।
  2. गिनती और स्टोर करें तत्वों की आवृत्ति नक्शे में और साथ ही साथ सरणी के मानों को दूरी सरणी में संग्रहीत करते हैं।
  3. दूरी सरणी को क्रमबद्ध करें।
  4. न्यूनतम n + 1 और आउटपुट 0 पर सेट करें।
  5. सरणी को पीछे छोड़ें, जबकि मैं
    1. उत्पादन के बीच अधिकतम और दूरी के अंतर के बीच का अंतर ज्ञात करें [i] और न्यूनतम और इसे आउटपुट में संग्रहीत करें।
    2. न्यूनतम और दूरी के मूल्य के बीच न्यूनतम खोजें [i] और इसे न्यूनतम पर संग्रहीत करें।
  6. वापसी आउटपुट।

व्याख्या

हमें एक पूर्णांक दिया जाता है और हमें दो तत्वों की आवृत्ति के बीच अधिकतम अंतर का पता लगाने की आवश्यकता होती है, ताकि अधिक आवृत्ति वाले तत्व न्यूनतम आवृत्ति के साथ एक पूर्णांक से अधिक भी हों और एक पूर्णांक से कम भी हों। हम उपयोग करने जा रहे हैं hashing और छँटाई जो हमें कुशल कोड बनाने में मदद करेगा। सबसे पहले, हम एक नक्शा और एक पूर्णांक सरणी घोषित करेंगे, जिसे दिए गए सरणी के समान आकार के साथ दूरी कहा जाता है।

सरणी तत्वों की आवृत्ति को संग्रहीत करने और उनकी गणना करने के लिए सरणी को ट्रेस करते समय हमें अपने एल्गोरिथ्म के अनुसार सरणी [i] के मूल्य को संग्रहीत करने की आवश्यकता होती है। हम आउटपुट का मान 0 और न्यूनतम से n + 1 तक सेट करेंगे। यह न्यूनतम मूल्य हमें सभी आवृत्तियों के बीच न्यूनतम पता लगाने में मदद करता है, और आउटपुट चर में, हम अपने अधिकतम अंतर को संग्रहीत करने जा रहे हैं। अब, हमें उस सरणी को क्रमबद्ध करने की आवश्यकता है जिसमें हम मानों (दूरी सरणी) को संग्रहीत करते हैं।

अब हम दूरी सरणी को पार कर लेंगे और हमें मान j तक ले जाना होगा क्योंकि पिछले ट्रैवर्सल में जब हम मानों को स्टोर कर रहे होते हैं तो हम j का मान बढ़ा रहे थे, इसलिए j का मान दूरी के लिए अधिकतम मान है। आर-पार करने के लिए सरणी। हमें आउटपुट और आवृत्ति और न्यूनतम मूल्य के बीच अंतर के बीच अधिकतम दूरी खोजने की आवश्यकता है। और इसे आउटपुट करने के लिए स्टोर करें और साथ ही हमें डिस्टेंस एरे एलिमेंट की न्यूनतम और फ्रीक्वेंसी के बीच न्यूनतम मूल्य को खोजने और इसे न्यूनतम स्टोर करने की आवश्यकता है। इसे तब तक जारी रखा जाएगा जब तक कि हम सभी मानों को एक दूरी सरणी में पार न कर दें। अंत में, हमारे पास आउटपुट में सबसे उपयुक्त उत्तर है और हम उस आउटपुट मान को वापस कर देंगे।

कार्यान्वयन

दो तत्वों की आवृत्ति के बीच अधिकतम अंतर के लिए सी ++ कार्यक्रम

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

दो तत्वों की आवृत्ति के बीच अधिकतम अंतर के लिए जावा कार्यक्रम

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

दो तत्वों की आवृत्ति के बीच अधिकतम अंतर के लिए जटिलता विश्लेषण

समय जटिलता

ओ (एन लॉग एन) जहां "N" सरणी में तत्वों की संख्या है।

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

पर) जहां "N" सरणी में तत्वों की संख्या है।