ഒരു അറേയിലെ ഉയർന്നതും കുറഞ്ഞതുമായ ആവൃത്തികൾ തമ്മിലുള്ള വ്യത്യാസം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു കോട്ട ഫാഷ് ഫോർകൈറ്റുകൾ 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. ഗണം maxfreq മുതൽ 0 വരെ minfreq ലേക്ക് n.
  4. മാപ്പ് സഞ്ചരിക്കുക:
    1. മാപ്പിലെ മാക്‌സ്‌ഫ്രെക്കും ആവൃത്തിയും തമ്മിലുള്ള പരമാവധി മൂല്യം കണ്ടെത്തി അത് മാക്‌സ്‌ഫ്രെക്കിൽ സംഭരിക്കുക.
    2. മാപ്പിലെ മിൻ‌ഫ്രെക്കും ആവൃത്തിയും തമ്മിലുള്ള ഏറ്റവും കുറഞ്ഞ മൂല്യം കണ്ടെത്തി അത് മിൻ‌ഫ്രെക്കിലേക്ക് സംഭരിക്കുക.
  5. മടങ്ങുക (maxfreq-minfreq).

വിശദീകരണം

ഞങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിരയുണ്ട്. ഒരു ശ്രേണിയിൽ നിലവിലുള്ള രണ്ട് വ്യത്യസ്ത സംഖ്യകളുടെ ഏറ്റവും ഉയർന്ന സംഭവവും ഏറ്റവും കുറഞ്ഞ സംഭവവും തമ്മിലുള്ള പരമാവധി വ്യത്യാസം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ്. ഈ ചോദ്യം പരിഹരിക്കുന്നതിന് ഹാഷിംഗ് ഒരു കാര്യക്ഷമമായ മാർഗം നൽകുന്നു. ഞങ്ങൾ ഒരു മാപ്പ് പ്രഖ്യാപിക്കാനും ഓരോ അറേ ഘടകത്തിന്റെയും ആവൃത്തികൾ കണക്കാക്കാനും ഒരേ സമയം മാപ്പിലേക്ക് ഘടകങ്ങളോടൊപ്പം ആവൃത്തികൾ സംഭരിക്കാനും പോകുന്നു.

അതിന്റെ മൂല്യം ഞങ്ങൾ സജ്ജീകരിക്കും maxfreq മുതൽ 0 വരെ minfreq മുതൽ n വരെ, അതായത്, അറേയുടെ ദൈർഘ്യം, കാരണം ഒരു ഘടകത്തിനും നൽകിയ അറേയുടെ വലുപ്പത്തേക്കാൾ വലിയ ആവൃത്തി ഇല്ല. ഞങ്ങൾ‌ മാപ്പിൽ‌ സഞ്ചരിച്ച് ഓരോ ഘടകങ്ങളും ഓരോന്നായി എടുക്കുകയും അതിന് ഏറ്റവും വലിയതോ താഴ്ന്നതോ ആയ ഒരു ഫ്രീക്വൻസി ഉണ്ടോ എന്ന് പരിശോധിക്കുകയും ചെയ്യും. പരമാവധി ആവൃത്തിയെ മറ്റൊരു വേരിയബിളിലേക്കും മിനിമം ഫ്രീക്വൻസി വ്യത്യസ്ത വേരിയബിളിലേക്കും വേർതിരിക്കുക. പരമാവധി ആവൃത്തിയും ഏറ്റവും കുറഞ്ഞ ആവൃത്തിയും തമ്മിലുള്ള വ്യത്യാസം ഞങ്ങൾ നൽകേണ്ടതുണ്ട്, അതിനാൽ ഞങ്ങൾ മടങ്ങും (maxfreq-minfreq).

നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം:

ഉദാഹരണം

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 minfreq നേക്കാൾ ചെറുതാണ്, അതിനാൽ minfreq = 3

  • 2: 2

maxfreq 2 നേക്കാൾ വലുതാണ്, അതിനാൽ maxfreq = 3

2 minfreq നേക്കാൾ ചെറുതാണ്, അതിനാൽ minfreq = 2

  • 3: 2

maxfreq 2 നേക്കാൾ വലുതാണ്, അതിനാൽ maxfreq = 3

Minfreq, minfreq = 2 എന്നിവയിൽ ഒന്നും മാറ്റിയിട്ടില്ല

  • 5: 1

maxfreq 1 നേക്കാൾ വലുതാണ്, അതിനാൽ maxfreq = 3

1 minfreq നേക്കാൾ ചെറുതാണ്, അതിനാൽ minfreq = 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) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. അറേയിലെ ഘടകങ്ങളുടെ ആവൃത്തികളുടെ ട്രാക്ക് സൂക്ഷിക്കുന്നതിലൂടെ ഞങ്ങൾ ഇവിടെ സഞ്ചരിച്ചു. ഇവയ്‌ക്കെല്ലാം O (N) സമയം മാത്രമേ ചെലവാകൂ.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. പരമാവധി, അവയെല്ലാം വ്യത്യസ്തമാണെങ്കിൽ നമുക്ക് n ഘടകങ്ങൾ സംഭരിക്കാൻ കഴിയും. സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.