Массивтегі айқын іргелес элементтер  


Күрделілік дәрежесі оңай
Жиі кіреді Coursera DE Шоу жорық IBM Кулиза Нагарро опера OYO бөлмелері Зохо
Array

Проблемалық мәлімдеме  

Бізде ан бүтін сан массив. «Массивтегі іргелес элементтер» мәселесі, егер мүмкін болса, массивтегі екі көршілес немесе көршілес элементтерді ауыстыру арқылы барлық іргелес сандар бір-біріне ұқсамайтын массивті алуға болатынын анықтауға мүмкіндік береді, содан кейін «ИӘ ”Болмаса“ ЖОҚ ”басып шығарыңыз.

мысал  

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

Бұл мысалда біз [2] arr [3] және [5] қатарларын сәйкесінше 2 және XNUMX-ге ауыстыру арқылы көршілес сандар жиымын ала аламыз.

Массивтегі айқын іргелес элементтер

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

Түсіндіру

Мәндерді ауыстырғаннан кейін де біз қажетті массивті ала алмаймыз.

Массивтегі көршілес элементтердің алгоритмі  

1. Declare a map.
2. Count and store the frequencies of each element of the array.
3. Set maxFreq to 0.
4. Get the maximum frequency of a number from the map.
5. Check if maxFreq is greater than the half-length of the array, means maxFreq >(n+1) / 2.
    1. If true, then print NO.
    2. Else print YES.

Түсіндіру  

Бізге бүтін массив берілген. Бізден белгілі іргелес элементтер мүмкін болатын массивті алуды анықтау сұралды. Егер мұндай массив мүмкін болмаса, онда ЖОҚ дегенді басып шығарыңыз ИӘ. Енді біз қажетті массивті алу үшін қанша санды ауыстыру керектігін тексеруіміз керек. Біз әр элементтің пайда болуын, сонымен қатар максималды пайда болу жиым ұзындығының жартысынан артық болмауын тексеруіміз керек. Егер массивтің ұзындығы 5. түрінде берілсе. Егер элемент массивте 3 рет кездесетін болса. Содан кейін массивті бірінші, үшінші және бесінші позицияларда қайта орналастыруға болады. Сонымен, массивтен белгілі іргелес элементтерді алуға болады.

Сондай-ақ, қараңыз
Сызықтық уақыттағы 3 өлшемді сұрыпталған тізбекті табыңыз

Біз жариялаймыз: а карта. Содан кейін біз массивті айналып өтіп, әр элементтің жиілігін санап шығамыз. Бір уақытта барлық элементтердің барлық жиіліктерін картаға сақтаңыз. Бізде 5 саннан тұратын массив бар делік, олардың екеуі массивте екі рет, ал екінші саны бір рет болды. Сонымен, біз массивтің әрбір элементінің жиілігін сақтаймыз. Элементтің барлық жиіліктерін сақтағаннан кейін. Біз maxFreq айнымалысын 0-ге қоямыз, онда максималды жиілікті анықтағаннан кейін элементтің максималды жиілік нөмірін сақтаймыз.

Ол үшін біз картаны айналып өтіп, егер бізде бұрын сақталған жиіліктен үлкен жиілік болса, әр элементті тексереміз. Осының көмегімен біз жиілік ретінде максималды санға ие боламыз және бұл жиілік массивтің ұзындығының жартысынан үлкен екенін тексереміз. Егер рас болса, онда ЖОҚ, ал ИӘ басып шығарыңыз.

код  

Массивтің нақты іргелес элементтеріне арналған C ++ коды

#include<bits/stdc++.h>
using namespace std;
void areDistinctAdjacent(int a[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[a[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        if (maxFreq < MAP[a[i]])
            maxFreq = MAP[a[i]];
    if (maxFreq > (n + 1) / 2)
        cout << "NO";
    else
        cout << "YES";
}
int main()
{
    int arr[] = { 3,5,5,3,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    areDistinctAdjacent(arr, n);
    return 0;
}

 

YES

Массивтегі көршілес элементтерге арналған Java коды

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

class adjacentDistinctElement
{
    static void areDistinctAdjacent(int a[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();

        for (int i = 0; i < n; ++i)
        {
            if(MAP.containsKey(a[i]))
            {
                int x = MAP.get(a[i]) + 1;
                MAP.put(a[i],x);
            }
            else
            {
                MAP.put(a[i],1);
            }

        }
        int maxFreq = 0;

        for (int i = 0; i < n; ++i)
            if (maxFreq < MAP.get(a[i]))
                maxFreq = MAP.get(a[i]);

        if (maxFreq > (n + 1) / 2)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
    public static void main (String[] args)
    {
        int arr[] = { 3,5,5,3,5 };
        int n = arr.length;
        areDistinctAdjacent(arr, n);
    }
}

YES

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

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

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

Сондай-ақ, қараңыз
Итеративті алдын ала тапсырыс беру

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

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