Максимальная разница между частотой двух элементов, при которой элемент с большей частотой также больше


Сложный уровень средний
Часто спрашивают в Accenture Акколит Амазонка VMware
массив Hash Сортировка

Предположим, у вас есть целое число массив. В постановке задачи предлагается определить максимальную разницу между частотой любых двух различных элементов данного массива, но элемент с большей частотой также должен быть больше по значению, чем другое целое число.

Пример

Входной сигнал:

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. Пройдите по массиву, пока я
    1. Найдите максимум между выходом и разницей между значением distance [i] и минимумом и сохраните его для выхода.
    2. Найдите минимум между минимумом и значением distance [i] и сохраните его как минимум.
  6. Возврат вывода.

объяснение

Нам дано целое число, и нам нужно выяснить максимальную разницу между частотой двух элементов, чтобы элемент с большей частотой также был больше, чем другое целое число с самой низкой частотой, а также был меньше большего целого числа. Мы собираемся использовать хеширования и сортировка что поможет нам сделать эффективный код. Сначала мы объявим карту и целочисленный массив с именем distance с тем же размером, что и данный массив.

При обходе массива для хранения и подсчета частоты элементов массива нам также необходимо сохранить значение array [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 (п войти п) в котором «Н» это количество элементов в массиве.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.