Већа је и максимална разлика између фреквенције два елемента, тако да елемент који има већу фреквенцију


Ниво тешкоће Средњи
Често питани у Аццентуре Аццолите амазонка ВМваре
Ред Хасх сортирање

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

Пример

Улаз:

арр [] = {2,4,4,4,3,2}

Излаз:

2

objašnjenje:

Учесталост 4 → 3

Учесталост 2 → 2

а учесталост 3 → 1

4 (3) - 3 (1) = 2 (Цели бројеви су такође већи и максимална учесталост).

Алгоритам

  1. Изјавите а Мапа и низ рецимо „удаљеност“ дужине н.
  2. Броји и чувај фреквенција елемената на мапу и истовремено сместите вредности низа у низ удаљености.
  3. Сортирај низ раздаљине.
  4. Поставите минимум на н + 1 и излаз на 0.
  5. Пређите низ, док и
    1. Пронађите максимум између излаза и разлике између вредности растојања [и] и минимума и сачувајте га на излазу.
    2. Пронађите минимум између минимума и вредности растојања [и] и сачувајте га на минимуму.
  6. Повратни излаз.

Објашњење

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

Док обилазимо низ ради складиштења и бројања учесталости елемената низа, такође треба да ускладиштимо вредност низа [и] према нашем алгоритму. Вредност излаза поставићемо на 0, а минималну на н + 1. Ова минимална вредност помаже нам да сазнамо минимум међу свим фреквенцијама, а у излазној променљивој ћемо сачувати своју максималну разлику. Сада треба да сортирамо низ у којем чувамо вредности (низ раздаљина).

Сада ћемо прећи низ раздаљине и треба да пређемо до вредности ј, јер смо у претходном прелазу, када смо чували вредности на даљину, повећавали вредност ј, па је вредност ј максимална вредност за удаљеност низ за прелазак горе. Морамо да пронађемо максимално растојање између излаза и разлику између фреквенције и минималне вредности. И сачувајте га за излаз, а такође такође морамо пронаћи минималну вредност између минимума и учесталости елемента низа дистанце и сачувати га на минимум. То ће се наставити све док не пређемо све вредности у низу дистанце. Напокон имамо најприкладнији одговор у излазу и вратићемо ту излазну вредност.

Имплементација

Ц ++ програм за максималну разлику између фреквенције два елемента

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

Јава програм за максималну разлику између фреквенције два елемента

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

Анализа сложености за максималну разлику између фреквенције два елемента

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

О (н лог н) где „Н“ је број елемената у низу.

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

Он) где „Н“ је број елемената у низу.