Массивдеги эң жогорку жана эң аз жыштыктардын айырмасы  


Кыйынчылык деңгээли жеңил
Көп суралган Citadel Fab Fourkites Roblox Tesla
согуштук тизме таштанды сорттоо

"Массивдеги эң жогорку жана эң аз жыштыктардын айырмасы" көйгөйүндө сизде ан бар деп ойлойбуз бүтүн согуштук тизме. Маселенин коюлушу массивдеги эки так сандын эң жогорку жыштыгы менен эң төмөнкү жыштыгынын ортосундагы максималдуу айырманы табууну сурайт.

мисал  

Массивдеги эң жогорку жана эң аз жыштыктардын айырмасытөөнөч

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 жыштыгы (Эң төмөнкү жыштык)

Algorithm  

  1. Декларация a карта.
  2. Массив элементинин жыштыгын сактоо жана эсептөө.
  3. коюлган maxfreq 0 жана minfreq үчүн n.
  4. Картаны кесип өтүңүз:
    1. Картадан maxfreq менен жыштыктын ортосундагы эң чоң маанини билип, maxfreq чейин сактаңыз.
    2. Картадан minfreq менен жыштыктын ортосундагы минималдуу маанини билип, minfreq чейин сактаңыз.
  5. Кайтуу (maxfreq-minfreq).

түшүндүрүү

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

ошондой эле
Бардык ич ара сүрөттөрдү 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 элементин сактай алабыз. Космостун татаалдыгы сызыктуу.