శ్రేణిలో అత్యధిక మరియు తక్కువ పౌన encies పున్యాల మధ్య వ్యత్యాసం  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది సిటాడెల్ Fab ఫోర్కైట్స్ Roblox టెస్లా
అర్రే హాష్ సార్టింగ్

“శ్రేణిలో అత్యధిక మరియు తక్కువ పౌన encies పున్యాల మధ్య వ్యత్యాసం” అనే సమస్య మీకు ఉందని అనుకుందాం పూర్ణ సంఖ్య అమరిక. శ్రేణిలోని రెండు విభిన్న సంఖ్యల యొక్క అత్యధిక పౌన frequency పున్యం మరియు తక్కువ పౌన frequency పున్యం మధ్య గరిష్ట వ్యత్యాసాన్ని తెలుసుకోవడానికి సమస్య ప్రకటన అడుగుతుంది.

ఉదాహరణ  

శ్రేణిలో అత్యధిక మరియు తక్కువ పౌన encies పున్యాల మధ్య వ్యత్యాసంపిన్

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

వివరణ

1 → 3 యొక్క ఫ్రీక్వెన్సీ (అత్యధిక పౌన frequency పున్యం)

5 → 1 యొక్క ఫ్రీక్వెన్సీ (అత్యల్ప పౌన frequency పున్యం)

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

వివరణ

5 → 4 యొక్క ఫ్రీక్వెన్సీ (అత్యధిక పౌన frequency పున్యం)

3 → 1 యొక్క ఫ్రీక్వెన్సీ (అత్యల్ప పౌన frequency పున్యం)

అల్గారిథం  

  1. ప్రకటించండి a మ్యాప్.
  2. శ్రేణి మూలకం యొక్క ఫ్రీక్వెన్సీని నిల్వ చేయండి మరియు లెక్కించండి.
  3. సెట్ maxfreq నుండి 0 మరియు minfreq కు n.
  4. మ్యాప్‌లో ప్రయాణించండి:
    1. మ్యాప్‌లోని మాక్స్‌ఫ్రెక్ మరియు ఫ్రీక్వెన్సీ మధ్య గరిష్ట విలువను కనుగొని దాన్ని మాక్స్ఫ్రెక్‌లో నిల్వ చేయండి.
    2. మ్యాప్‌లోని మిన్‌ఫ్రెక్ మరియు ఫ్రీక్వెన్సీ మధ్య కనీస విలువను కనుగొని మిన్‌ఫ్రెక్‌లో నిల్వ చేయండి.
  5. తిరిగి (మాక్స్ఫ్రెక్-మిన్‌ఫ్రేక్).

వివరణ

మాకు పూర్ణాంకాల శ్రేణి ఉంది. శ్రేణిలో ఉన్న రెండు విభిన్న సంఖ్యల యొక్క అత్యధిక సంఘటన మరియు అత్యల్ప సంఘటనల మధ్య గరిష్ట వ్యత్యాసాన్ని కనుగొనడం మా పని. మేము ఉపయోగించబోతున్నాం హాషింగ్. ఈ ప్రశ్నను పరిష్కరించడానికి హాషింగ్ సమర్థవంతమైన మార్గాన్ని అందిస్తుంది. మేము ఒక మ్యాప్‌ను ప్రకటించి, ప్రతి శ్రేణి మూలకం యొక్క పౌన encies పున్యాలను లెక్కించబోతున్నాము మరియు ఏకకాలంలో మాప్‌లోని మూలకాలతో పాటు పౌన encies పున్యాలను నిల్వ చేస్తాము.

ఇది కూడ చూడు
అన్ని సబ్‌రేలను 0 మొత్తంతో ముద్రించండి

అప్పుడు మేము విలువను సెట్ చేస్తాము maxfreq నుండి 0 మరియు minfreq n కి, అనగా, శ్రేణి యొక్క పొడవు ఎందుకంటే ఇచ్చిన మూలకం యొక్క పరిమాణం కంటే ఎక్కువ మూలకం ఫ్రీక్వెన్సీ లేదు. మేము మ్యాప్‌లో ప్రయాణించి, ప్రతి మూలకాన్ని ఒక్కొక్కటిగా ఎంచుకొని, ఫ్రీక్వెన్సీ గొప్పదా లేదా తక్కువ అని తనిఖీ చేస్తాము. గరిష్ట పౌన frequency పున్యాన్ని వేరే వేరియబుల్‌కు మరియు కనీస ఫ్రీక్వెన్సీని వేరే వేరియబుల్‌కు వేరు చేయండి. మేము గరిష్ట పౌన frequency పున్యం మరియు అత్యల్ప పౌన frequency పున్యం మధ్య వ్యత్యాసాన్ని తిరిగి ఇవ్వాలి, కాబట్టి మేము తిరిగి వస్తాము (మాక్స్ఫ్రెక్-మిన్ఫ్రెక్).

ఒక ఉదాహరణ తీసుకుందాం:

ఉదాహరణ

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

మేము మొదట శ్రేణిని దాటినప్పుడు, మేము మూలకాన్ని మరియు వాటి సంభవించిన వాటి సంఖ్యను మ్యాప్‌లో ఉంచుతాము, ప్రయాణించిన తర్వాత మనకు మ్యాప్ ఇలా ఉంటుంది:

పటం: {1: 3, 2: 2, 3: 2, 5: 1}

ఇప్పుడు, మాప్‌లోని ప్రతి మూలకం యొక్క సంఘటనలు మనకు ఉన్నాయి, మేము మ్యాప్‌లో ప్రయాణించబోతున్నాము మరియు మ్యాప్ నుండి ప్రతి మూలకాన్ని ఎంచుకొని వాటి ఫ్రీక్వెన్సీని తనిఖీ చేస్తాము, ఇది ఎక్కువ ప్రస్తుత ఫ్రీక్వెన్సీ లేదా మాక్స్ఫ్రెక్ మరియు ఇది కనీస ప్రస్తుత ఫ్రీక్వెన్సీ లేదా minfreq మరియు దానిని వరుసగా maxfreq మరియు minfreq కు నిల్వ చేయండి.

  • 1: 3

3 మాక్స్ఫ్రెక్ కంటే ఎక్కువ, కాబట్టి మాక్స్ఫ్రెక్ = 3

3 మిన్‌ఫ్రెక్ కంటే చిన్నది, కాబట్టి మిన్‌ఫ్రెక్ = 3

  • 2: 2

maxfreq 2 కన్నా ఎక్కువ, కాబట్టి maxfreq = 3

2 మిన్‌ఫ్రెక్ కంటే చిన్నది, కాబట్టి మిన్‌ఫ్రెక్ = 2

  • 3: 2

maxfreq 2 కన్నా ఎక్కువ, కాబట్టి maxfreq = 3

Minfreq, minfreq = 2 లో ఏమీ మార్చబడలేదు

  • 5: 1

maxfreq 1 కన్నా ఎక్కువ, కాబట్టి maxfreq = 3

1 మిన్‌ఫ్రెక్ కంటే చిన్నది, కాబట్టి మిన్‌ఫ్రెక్ = 1

ఇది కూడ చూడు
పెయింటింగ్ కంచె అల్గోరిథం

మరియు మేము మాక్స్ఫ్రెక్-మిన్ఫ్రెక్ between (3-1) = 2 మధ్య వ్యత్యాసాన్ని తిరిగి ఇస్తాము.

కోడ్  

శ్రేణిలో అత్యధిక మరియు తక్కువ పౌన encies పున్యాల మధ్య వ్యత్యాసాన్ని కనుగొనడానికి 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

శ్రేణిలో అత్యధిక మరియు తక్కువ పౌన encies పున్యాల మధ్య వ్యత్యాసాన్ని కనుగొనడానికి జావా కోడ్

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 మూలకాలను నిల్వ చేయవచ్చు. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.