Екі элементтің жиілігі арасындағы максималды айырмашылық, мысалы, жиілігі үлкен элемент көп  


Күрделілік дәрежесі орта
Жиі кіреді Accenture Акколит Amazon VMware
Array 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. Массивті өтіңіз, ал i
    1. Шығару мен максималды арақашықтық арасындағы айырмашылық пен максимумды тауып, оны шығару үшін сақтаңыз.
    2. [I] арақашықтықтың минимумы мен мәні арасындағы минималды тауып, оны минимумға дейін сақтаңыз.
  6. Шығуды қайтару.

Түсіндіру  

Бізге бүтін сан берілген және біз екі элементтің жиілігі арасындағы ең үлкен айырмашылықты табуымыз керек, сонда жиілігі үлкен элемент ең төменгі жиіліктегі басқа бүтін саннан үлкен болуы керек, сонымен бірге үлкен бүтін саннан кіші болуы керек. Біз қолданамыз Хэш және сұрыптау бұл бізге тиімді код жасауға көмектеседі. Алдымен біз берілген массивтің өлшемімен бірдей қашықтық деп аталатын карта мен бүтін массивті жариялаймыз.

Сондай-ақ, қараңыз
График үшін бірінші іздеу (BFS)

Массив элементтерін сақтау және есептеу үшін жиымнан өтіп бара жатқанда [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) қайда «N» - бұл массивтегі элементтер саны.

Сондай-ақ, қараңыз
Массивтегі айқын іргелес элементтер

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.