Максималната разлика между честотата на два елемента, така че елементът с по-голяма честота също е по-голяма


Ниво на трудност M
Често задавани в Accenture Аколит Амазонка VMware
Array Хашиш сортиране

Да предположим, че имате цяло число масив. Изложението на проблема иска да открие максималната разлика между честотата на всеки два различни елемента от даден масив, но елементът с по-голяма честота също трябва да бъде по-голям по стойност от другото цяло число.

Пример

Вход:

arr [] = {2,4,4,4,3,2}

Изход:

2

Обяснение:

Честотата на 4 → 3

Честотата на 2 → 2

и честотата на 3 → 1

4 (3) - 3 (1) = 2 (Целите числа също са по-големи и с максимална честота).

алгоритъм

  1. Декларирайте а карта и масив казва "разстояние" с дължина n.
  2. Бройте и съхранявайте честота на елементите в картата и едновременно съхранява стойностите на масива в масив от разстояние.
  3. Сортирайте масива за разстояние.
  4. Задайте минимум на n + 1 и изход на 0.
  5. Прекоси масива, докато i
    1. Намерете максимума между изхода и разликата между стойността на разстоянието [i] и минимума и го запазете за изход.
    2. Намерете минимума между минимума и стойността на разстоянието [i] и го запазете до минимум.
  6. Връщане на изхода.

Обяснение

Дадено ни е цяло число и трябва да открием максималната разлика между честотата на два елемента, така че елементът с по-голяма честота също да е по-голям от друго цяло число с най-ниска честота и също да е по-малък от по-голямо цяло число. Ще използваме хеширане и сортиране което ще ни помогне да направим ефективен код. Първо ще декларираме карта и цяло число масив, наречен разстояние със същия размер като на даден масив.

Докато обхождаме масива, за да съхраняваме и броим честотата на елементите на масива, ние също трябва да съхраняваме стойността на масива [i] според нашия алгоритъм. Ще зададем стойността на изхода на 0 и минимална на n + 1. Тази минимална стойност ни помага да открием минимума сред всички честоти, а в изходната променлива ще съхраним максималната си разлика. Сега трябва да сортираме масива, в който съхраняваме стойностите (масив от разстояние).

Ще прекосим масива от разстояние сега и трябва да преминем до стойността j, тъй като в предишното обхождане, когато съхраняваме стойностите в разстояние, увеличавахме стойността на j, така че стойността на j е максималната стойност за разстоянието масив за пресичане нагоре. Трябва да намерим максималното разстояние между изхода и разликата между честотата и минималната стойност. И го съхраняваме за извеждане, а също така трябва да намерим минималната стойност между минималното и честотата на елемента от масив за разстояние и да го съхраним до минимум. Това ще продължи, докато не преминем всички стойности в масив от разстояние. Най-накрая имаме най-подходящия отговор в изхода и ще върнем тази изходна стойност.

изпълнение

C ++ програма за максимална разлика между честотата на два елемента

#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

Java програма за Максимална разлика между честотата на два елемента

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

Анализ на сложността за максимална разлика между честотата на два елемента

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

O (n log n) където "н" е броят на елементите в масива.

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

О (п) където "н" е броят на елементите в масива.