अ‍ॅरेमध्ये सर्वाधिक आणि कमीतकमी फ्रिक्वेन्सी दरम्यान फरक


अडचण पातळी सोपे
वारंवार विचारले किल्ला फॅब फोरकाइट्स Roblox टेस्ला
अरे हॅश वर्गीकरण

“अ‍ॅरे मधील सर्वाधिक आणि किमान वारंवारते दरम्यान फरक” ही समस्या नमूद करते की समजा आपल्याकडे आहे पूर्णांक अॅरे. अ‍ॅरेमधील दोन भिन्न संख्यांमधील सर्वाधिक वारंवारता आणि सर्वात कमी वारंवारता दरम्यान जास्तीत जास्त फरक शोधण्यासाठी समस्या विधान विचारते.

उदाहरण

अ‍ॅरेमध्ये सर्वाधिक आणि कमीतकमी फ्रिक्वेन्सी दरम्यान फरक

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

स्पष्टीकरण

1 → 3 ची वारंवारता (उच्चतम वारंवारता)

5 → 1 ची वारंवारता (सर्वात कमी वारंवारता)

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

स्पष्टीकरण

5 → 4 ची वारंवारता (उच्चतम वारंवारता)

3 → 1 ची वारंवारता (सर्वात कमी वारंवारता)

अल्गोरिदम

  1. घोषित ए नकाशा.
  2. अ‍ॅरे घटकाची वारंवारता संचयित आणि मोजा.
  3. सेट करा मॅक्सफ्रेक 0 आणि minfreq ते n.
  4. नकाशा ओलांडू:
    1. नकाशामध्ये मॅक्सफ्रेक आणि वारंवारता दरम्यानचे अधिकतम मूल्य शोधा आणि ते मॅक्सफ्रेकमध्ये संचयित करा.
    2. नकाशामध्ये मिनफ्रेक आणि वारंवारता दरम्यान किमान मूल्य शोधा आणि ते मिनफ्रेकमध्ये संचयित करा.
  5. रिटर्न (मॅक्सफ्रेक-मिन्फ्रेक).

स्पष्टीकरण

आपल्याकडे पूर्णांक संख्या आहे. अ‍ॅरेमध्ये उपस्थित असलेल्या दोन भिन्न संख्येमधील सर्वाधिक घटना आणि सर्वात कमी घटना यांच्यातील जास्तीत जास्त फरक शोधणे हे आपले कार्य आहे. आम्ही वापरणार आहोत हॅशिंग. हॅशिंग हा प्रश्न सोडविण्याचा एक प्रभावी मार्ग प्रदान करतो. आम्ही नकाशा घोषित करणार आहोत आणि प्रत्येक अ‍ॅरे घटकाची वारंवारता मोजू आणि त्या घटकांसह वारंवारता नकाशामध्ये संचयित करत आहोत.

नंतर व्हॅल्यू सेट करू मॅक्सफ्रेक 0 आणि minfreq ते n पर्यंत, म्हणजे अ‍ॅरेची लांबी कारण दिलेल्या घटकाच्या आकारापेक्षा कोणत्याही घटकाची वारंवारता जास्त नसते. आम्ही नकाशा ओलांडू आणि प्रत्येक घटक एक-एक करून निवडतो आणि त्यातील वारंवारता सर्वात मोठी किंवा सर्वात कमी आहे का ते तपासू. जास्तीत जास्त वारंवारता भिन्न चल आणि किमान वारंवारता भिन्न व्हेरिएबलमध्ये विभक्त करा. आम्हाला जास्तीत जास्त वारंवारता आणि सर्वात कमी वारंवारता यातील फरक परत करणे आवश्यक आहे, म्हणून आम्ही परत येऊ (मॅक्सफ्रेक-मिन्फ्रेक).

चला एक उदाहरण घेऊ:

उदाहरण

अरे [] = {1, 2, 3, 1, 5, 2, 3, 1}

जेव्हा आम्ही प्रथम अ‍ॅरेला मागे टाकतो, तेव्हा आम्ही घटक आणि त्यातील काही घटना नकाशात ठेवू, आम्ही ट्रॅव्हर्स केल्यावर आमच्याकडे नकाशा असा असेलः

नकाशा: {1: 3, 2: 2, 3: 2, 5: 1}

आता, आपल्याकडे नकाशामध्ये प्रत्येक घटकाची घटना घडली आहे, आम्ही नकाशाला मागे टाकत आहोत, आणि प्रत्येक घटक नकाशावरून निवडत आहोत आणि त्यांची वारंवारता तपासणार आहोत, जे सध्याची वारंवारता किंवा मॅक्सफ्रेक जास्त आहे आणि किमान वर्तमान वारंवारता किंवा minfreq आणि त्यास अनुक्रमे मॅक्सफ्रेक आणि मिनीफ्रेकवर ठेवा.

  • 1: 3 →

3 हे मॅक्सफ्रेकपेक्षा मोठे आहे, म्हणून मॅक्सफ्रेक = 3

3 मिनफ्रेकपेक्षा लहान आहे, म्हणून मिनफ्रेक = 3

  • 2: 2 →

मॅक्सफ्रेक 2 पेक्षा मोठे आहे, म्हणून मॅक्सफ्रेक = 3

2 मिनफ्रेकपेक्षा लहान आहे, म्हणून मिनफ्रेक = 2

  • 3: 2 →

मॅक्सफ्रेक 2 पेक्षा मोठे आहे, म्हणून मॅक्सफ्रेक = 3

मिनफ्रेक, मिनफ्रेक = 2 ​​मध्ये काहीही बदलले नाही

  • 5: 1 →

मॅक्सफ्रेक 1 पेक्षा मोठे आहे, म्हणून मॅक्सफ्रेक = 3

1 मिनफ्रेकपेक्षा लहान आहे, म्हणून मिनफ्रेक = 1

आणि आम्ही मॅक्सफ्रेक-मिनिफ्रेक → (3-1) = 2 मधील फरक परत करू.

कोड

अ‍ॅरे मधील सर्वाधिक आणि किमान वारंवारते दरम्यान फरक शोधण्यासाठी सी ++ कोड

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

अ‍ॅरेमध्ये सर्वाधिक आणि किमान वारंवारते दरम्यान फरक शोधण्यासाठी जावा कोड

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

गुंतागुंत विश्लेषण

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. येथे आम्ही त्यांच्या फ्रिक्वेन्सीचा मागोवा ठेवत अ‍ॅरेच्या घटकांमधून सहजपणे पुढे गेलो आहोत. या सर्वांसाठी केवळ ओ (एन) वेळ लागतो.

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. अधिकतर, आम्ही सर्व घटक वेगळे असल्यास एन घटक संचयित करू शकतो. जागेची जटिलता रेखीय आहे.