Разлика између највиших и најмањих фреквенција у низу


Ниво тешкоће Лако
Често питани у Цитадела Фаб Фоуркитес роблок Тесла
Ред Хасх сортирање

Проблем „Разлика између највеће и најмање фреквенције у низу“ наводи да претпостављамо да имате цео број поредак. Изјава о проблему тражи да се утврди максимална разлика између највеће и најниже фреквенције два различита броја у низу.

Пример

Разлика између највиших и најмањих фреквенција у низу

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. и минфрек до n.
  4. Пређите мапу:
    1. Дознајте максималну вредност између макфрек и фреквенције на мапи и сачувајте је у макфрек.
    2. Пронађите минималну вредност између минфрек-а и фреквенције на мапи и похраните је у минфрек.
  5. Повратак (макфрек-минфрек).

Објашњење

Имамо низ целих бројева. Наш задатак је да откријемо максималну разлику између највеће и најмање појаве два различита броја присутна у низу. Користићемо хасхинг. Хасхинг пружа ефикасан начин за решавање овог питања. Прогласићемо мапу и избројати фреквенције сваког елемента низа и истовремено похранити фреквенције заједно са елементима у мапу.

Тада ћемо поставити вредност од макфрек до 0. и минфрек на н, тј. дужину низа јер ниједан елемент нема фреквенцију већу од величине датог низа. Прећи ћемо мапу и покупити сваки елемент један по један и проверити да ли је фреквенција највећа или најмања. Одвојите максималну фреквенцију на другу променљиву, а минималну на другу променљиву. Морамо да вратимо разлику између максималне и најниже фреквенције, па ћемо се вратити (макфрек-минфрек).

Узмимо пример:

Пример

арр [] = {1, 2, 3, 1, 5, 2, 3, 1}

Када први пут пређемо низ, ставит ћемо елемент и број појављивања на мапу, након преласка имаћемо карту као:

Мапа: {1: 3, 2: 2, 3: 2, 5: 1}

Сада имамо појаве сваког елемента на мапи, прећи ћемо мапу и подићи сваки елемент са карте и проверити њихову фреквенцију, која је већа тренутна фреквенција или макфрек и која је минимална тренутна фреквенција или минфрек и сачувајте га у макфрек односно минфрек.

  • 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

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Овде смо једноставно прешли преко елемената низа водећи евиденцију њихових фреквенција. Све ово кошта само О (Н) време.

Сложеност простора

Он) где „Н“ је број елемената у низу. Можемо сачувати највише н елемената ако су сви различити. Сложеност простора је линеарна.