एर्रेमा उच्चतम र कम से कम फ्रिक्वेन्सीहरू बीच भिन्नता


कठिनाई तह सजिलो
बारम्बार सोधिन्छ Citadel फेब फोरकाइट्स Roblox tesla
एरे हैश क्रमबद्ध

समस्या "एर्रेमा उच्चतम र कम से कम फ्रिक्वेन्सीहरू बीच भिन्नता" ले भन्छ कि मानौं तपाईंसँग एक छ पूर्णांक array। समस्या कथनले एर्रेमा दुई भिन्न संख्याको उच्च आवृत्ति र न्यूनतम फ्रिक्वेन्सी बीचमा अधिकतम भिन्नता पत्ता लगाउन सोध्छ।

उदाहरणका

एर्रेमा उच्चतम र कम से कम फ्रिक्वेन्सीहरू बीच भिन्नता

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

स्पष्टीकरण

१ → Fre (उच्चतम आवृत्ति) को फ्रिक्वेन्सी

→ → १ को फ्रिक्वेन्सी (न्यूनतम फ्रिक्वेन्सी)

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

स्पष्टीकरण

१ → Fre (उच्चतम आवृत्ति) को फ्रिक्वेन्सी

→ → १ को फ्रिक्वेन्सी (न्यूनतम फ्रिक्वेन्सी)

अल्गोरिदम

  1. घोषणा गर्नुहोस् नक्सा.
  2. एर्रे तत्वको फ्रिक्वेन्सी स्टोर र गणना गर्नुहोस्।
  3. सेट maxfreq ० र minfreq लाई n.
  4. नक्सा पार गर्नुहोस्:
    1. नक्शामा अधिकतम मूल्य र फ्रिक्वेन्सी बीच अधिकतम मान पत्ता लगाउनुहोस् र यसलाई म्याक्सफ्रेकमा भण्डार गर्नुहोस्।
    2. नक्शामा minfreq र फ्रिक्वेन्सी बीच न्यूनतम मान पत्ता लगाउनुहोस् र यसलाई minfreq भण्डार गर्नुहोस्।
  5. फिर्ती (maxfreq-minfreq)।

स्पष्टीकरण

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

त्यसो भए हामी यसको मान सेट गर्नेछौं maxfreq ० र minfreq to n, अर्थात्, एर्रेको लम्बाई किनकि कुनै एलिमेन्टले दिएको एर्रेको साइज भन्दा ठूलो फ्रिक्वेन्सी हुँदैन। हामी नक्सा पार गर्नेछौं र प्रत्येक तत्व एक एक गरी उठाउँदैछौं र जाँच गर्छौं कि यो फ्रिक्वेन्सी सबैभन्दा ठूलो वा न्यून छ। अधिकतम फ्रिक्वेन्सी बिभिन्न चलमा र न्यूनतम फ्रिक्वेन्सी बिभिन्न भेरिएबलमा अलग गर्नुहोस्। हामीले अधिकतम फ्रिक्वेन्सी र न्यूनतम फ्रिक्वेन्सी बीच फर्कनु आवश्यक छ, त्यसैले हामी फर्कने छौं (maxfreq-minfreq)।

हामी एक उदाहरण लिनुहोस्:

उदाहरणका

एर [] = {१, २,,, १,,, २,,, १}

जब हामी एर्रेलाई पहिलो पटक ट्रान्सभर्स गर्दछौं, हामी एलिमेन्ट र उनीहरूको कुनै घटनाहरू नक्शामा राख्नेछौं, ट्र्याभर्स पछि हामीसँग नक्सा यस्तै हुनेछ:

नक्शा: {१:,, २: २,:: २,:: १}

अब हामीसँग मानचित्रमा प्रत्येक तत्त्वका घटनाहरू छन्, हामी नक्सा पार गर्न जाँदैछौं, र प्रत्येक तत्वलाई नक्साबाट टिप्दैछौं र तिनीहरूको फ्रिक्वेन्सी जाँच्दछौं, जुन हालको फ्रिक्वेन्सी वा म्याक्सफ्रेक हो र जुन न्यूनतम वर्तमान फ्रिक्वेन्सी हो वा minfreq र यसलाई क्रमश: maxfreq र minfreq भण्डार गर्नुहोस्।

  • १: → →

म्याक्सफ्रेक भन्दा ठूलो छ, त्यसैले म्याक्सफ्रेक =।

Min minfreq भन्दा सानो छ, त्यसैले minfreq =।

  • १: → →

maxfreq २ भन्दा ठूलो छ, त्यसैले maxfreq =।

Min minfreq भन्दा सानो छ, त्यसैले minfreq =।

  • १: → →

maxfreq २ भन्दा ठूलो छ, त्यसैले maxfreq =।

केहि पनि बदलिएको छैन minfreq, minfreq = 2

  • १: → →

maxfreq २ भन्दा ठूलो छ, त्यसैले maxfreq =।

Min minfreq भन्दा सानो छ, त्यसैले minfreq =।

र हामी म्याक्सफ्रेक- minfreq 3 (-1-१) बीचमा फर्काउँछौं = २।

कोड

C ++ कोड एर्रेमा उच्चतम र कम से कम फ्रिक्वेन्सीहरूको बीच भिन्नता पत्ता लगाउन

#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

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

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। यहाँ हामी एर्रेको एलिमेन्टहरुमा मात्र ट्रयाभर्स गर्दै छौं आफ्ना फ्रिक्वेन्सीहरूको ट्रयाक राख्दै। यी सबैको लागि O (N) समय मात्र खर्च हुन्छ।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। अधिकमा, हामी n तत्वहरू भण्डारण गर्न सक्दछौं यदि ती सबै फरक छन्। ठाउँ जटिलता रैखिक छ।