Жиымдағы ең жоғары және ең кіші жиіліктер арасындағы айырмашылық  


Күрделілік дәрежесі оңай
Жиі кіреді Цитадель Фаб Фуркиттер Roblox Tesla
Array Hash Сұрыптау

«Жиымдағы ең жоғары және ең кіші жиіліктердің арасындағы айырмашылық» мәселесі сізде бар деп болжайды бүтін сан массив. Мәселе қоюы массивтегі екі бөлек санның ең жоғары жиілігі мен ең төменгі жиілігі арасындағы максималды айырмашылықты анықтауды сұрайды.

мысал  

Жиымдағы ең жоғары және ең кіші жиіліктер арасындағы айырмашылықтүйреуіш

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

Түсіндіру

1 → 3 жиілігі (ең жоғары жиілік)

5 → 1 жиілігі (ең төменгі жиілік)

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

Түсіндіру

5 → 4 жиілігі (ең жоғары жиілік)

3 → 1 жиілігі (ең төменгі жиілік)

Алгоритм  

  1. Декларация а карта.
  2. Массив элементінің жиілігін сақтаңыз және санаңыз.
  3. жиынтық maxfreq 0-ге және minfreq дейін n.
  4. Картадан өту:
    1. Картадағы maxfreq мен жиілік арасындағы максималды мәнді анықтап, maxfreq деңгейіне дейін сақтаңыз.
    2. Картадан minfreq мен жиілік арасындағы минималды мәнді анықтап, minfreq деңгейіне дейін сақтаңыз.
  5. Қайту (maxfreq-minfreq).

Түсіндіру

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

Сондай-ақ, қараңыз
Барлық қосымшаларды 0 сомасымен басып шығарыңыз

Сонда біз мәнін орнатамыз maxfreq 0-ге және minfreq n-ге дейін, яғни массивтің ұзындығы, өйткені бірде-бір элемент берілген жиым өлшемінен үлкен жиілікке ие емес. Біз картадан өтіп, әрбір элементті бір-бірлеп жинаймыз және оның жиілігі ең үлкен не ең төменгі екенін тексереміз. Максималды жиілікті басқа айнымалыға және минималды жиілікті әртүрлі айнымалыға бөліңіз. Біз максималды жиілік пен ең төменгі жиілік арасындағы айырмашылықты қайтаруымыз керек, сондықтан біз ораламыз (maxfreq-minfreq).

Мысал алайық:

мысал

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

Біз массивті бірінші айналып өткенде, элементті және олардың болмауын картаға енгіземіз, өткеннен кейін бізде карта келесідей болады:

Карта: {1: 3, 2: 2, 3: 2, 5: 1}

Енді бізде картада әр элементтің пайда болуы бар, біз картадан өтіп, әр элементті картадан алып, олардың жиілігін тексереміз, бұл үлкен ток жиілігі немесе maxfreq, ал ең аз ток жиілігі немесе minfreq және оны maxfreq және minfreq сәйкесінше сақтаңыз.

  • 1: 3 →

3 maxfreq-тен үлкен, сондықтан maxfreq = 3

3 minfreq-тен кіші, сондықтан minfreq = 3

  • 2: 2 →

maxfreq 2-ден үлкен, сондықтан maxfreq = 3

2 minfreq-тен кіші, сондықтан minfreq = 2

  • 3: 2 →

maxfreq 2-ден үлкен, сондықтан maxfreq = 3

Minfreq-де ештеңе өзгермейді, minfreq = 2

  • 5: 1 →

maxfreq 1-ден үлкен, сондықтан maxfreq = 3

1 minfreq-тен кіші, сондықтан minfreq = 1

Сондай-ақ, қараңыз
Кескіндеме қоршау алгоритмі

Maxfreq-minfreq → (3-1) = 2 арасындағы айырмашылықты қайтарамыз.

код  

Массивтегі ең жоғарғы және ең кіші жиіліктер арасындағы айырмашылықты табу үшін C ++ коды

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

Массивтегі ең жоғарғы және ең кіші жиіліктер арасындағы айырмашылықты табу үшін Java коды

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

Күрделілікті талдау  

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Бұл жерде біз жиіліктің жай-күйін қадағалайтын жиым элементтерін араладық. Мұның бәрі тек O (N) уақытты алады.

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

O (N) қайда «N» - бұл массивтегі элементтер саны. Ең көп дегенде, егер олардың барлығы бөлек болса, біз n элементті сақтай аламыз. Кеңістіктің күрделілігі сызықтық болып табылады.