Երկու տարրերի հաճախականության առավելագույն տարբերությունն այնպիսին է, որ ավելի մեծ հաճախություն ունեցող տարրը նույնպես ավելի մեծ է


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Accenture Ակոլիտ Amazon VMware
Դասավորություն Խանգարել դասավորում

Ենթադրենք, դուք ունեք ամբողջ թիվ դասավորություն, Խնդրի հայտարարությունը խնդրում է պարզել տվյալ զանգվածի ցանկացած երկու տարբեր տարրերի հաճախության առավելագույն տարբերությունը, բայց ավելի մեծ հաճախություն ունեցող տարրը պետք է նաև արժեքով ավելի մեծ լինի, քան մյուս ամբողջ ամբողջ թիվը:

Օրինակ

Մուտք:

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. Վերադարձի արդյունքը:

բացատրություն

Մեզ տրված է ամբողջ թիվ, և մենք պետք է պարզենք առավելագույն տարբերությունը երկու տարրերի հաճախության միջև, այնպես որ ավելի մեծ հաճախություն ունեցող տարրը պետք է նաև ավելի մեծ լինի, քան մեկ այլ ամբողջ թվով ամենացածրը և ավելի փոքր լինի, քան ավելի մեծ ամբողջ թիվը: Մենք պատրաստվում ենք օգտագործել Հեշինգ և տեսակավորում ինչը կօգնի մեզ արդյունավետ կոդ կազմել: Նախ, մենք կհայտարարենք քարտեզ և ամբողջական զանգված, որը կոչվում է հեռավորություն, նույն չափի, ինչպես տրված զանգվածը:

Traանգվածը անցնելիս զանգվածի տարրերի հաճախականությունը պահելու և հաշվելու համար մենք նաև պետք է պահենք զանգվածի [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

Բարդության վերլուծություն երկու տարրերի հաճախականության առավելագույն տարբերության համար

Timeամանակի բարդություն

O (n տեղեկամատյան n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: