Разлика помеѓу највисоките и најмалите фреквенции во низата


Ниво на тешкотија Лесно
Често прашувано во Цитаделата Fab Фуркити 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 и минфрек до n.
  4. Поминете ја картата:
    1. Откријте ја максималната вредност помеѓу maxfreq и фреквенцијата на картата и зачувајте ја на maxfreq.
    2. Откријте ја минималната вредност помеѓу minfreq и фреквенцијата на картата и чувајте ја во minfreq.
  5. Враќање (maxfreq-minfreq).

Објаснување

Имаме низа цели броеви. Нашата задача е да ја откриеме максималната разлика помеѓу најголемата и најмалата појава на два посебни броја присутни во низата. Е користиме хашинг. Хаширањето обезбедува ефикасен начин за решавање на ова прашање. Toе декларираме мапа и ќе ги броиме фреквенциите на секој елемент во низата и истовремено ги зачувуваме фреквенциите заедно со елементите во картата.

Тогаш ќе ја поставиме вредноста на maxfreq до 0 и минфрек до n, односно должината на низата бидејќи ниту еден елемент нема фреквенција поголема од големината на дадената низа. Traе ја поминеме картата и ќе ги собереме секој елемент еден по еден и ќе провериме дали има најголема или најниска фреквенција. Одделете ја максималната фреквенција на друга променлива и минималната фреквенција на различна променлива. Треба да ја вратиме разликата помеѓу максималната и најмалата фреквенција, така што ќе се вратиме (maxfreq-minfreq).

Да земеме пример:

пример

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

Кога првпат ќе ја пресечеме низата, ќе ги ставиме елементот и нивното не појавување во картата, по пресекот ќе ја имаме мапата како:

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

Сега, имаме појава на секој елемент на картата, ние ќе ја пресечеме картата и ќе го земеме секој елемент од картата и ќе ја провериме нивната фреквенција, што е поголема фреквенција на струјата или maxfreq и која е минималната фреквенција на струјата или minfreq и чувајте го соодветно на maxfreq и minfreq.

  • 1: 3

3 е поголем од maxfreq, па maxfreq = 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

И ќе ја вратиме разликата помеѓу maxfreq-minfreq → (3-1) = 2.

Код

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

Java код за да се најде Разликата помеѓу највисоките и најмалите фреквенции во низата

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 елементи ако сите се различни. Комплексноста на просторот е линеарна.