એરેમાં સૌથી વધુ અને ઓછામાં ઓછી આવર્તન વચ્ચેનો તફાવત


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સિટાડેલ ફેબ ફોરકાઇટ્સ 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. નકશામાં મેક્સફ્રેક અને આવર્તન વચ્ચેનું મહત્તમ મૂલ્ય શોધી કા itો અને તેને મેક્સફ્રેક પર સ્ટોર કરો.
    2. નકશામાં મિનફ્રેક અને આવર્તન વચ્ચેનું ન્યુનત્તમ મૂલ્ય શોધી કાfો અને તેને મિનફ્રેક પર સ્ટોર કરો.
  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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. અહીં અમે એરેના તત્વો પર તેમની આવર્તનનો ટ્ર keepingક રાખીને ફક્ત આગળ નીકળી ગયા છે. આ બધાની કિંમત ફક્ત ઓ (એન) સમય છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. વધુમાં વધુ, જો આપણે બધા તત્વો અલગ હોય તો અમે n તત્વો સંગ્રહિત કરી શકીએ છીએ. જગ્યાની જટિલતા રેખીય છે.