Изразити суседни елементи у низу  


Ниво тешкоће Лако
Често питани у Цоурсера ДЕ Схав Пешачење ИБМ- Кулиза Нагарро радити ОИО собе Зохо
Ред

Изјава о проблему  

Претпоставимо да имамо цео број поредак. Проблем „Различити суседни елементи у низу“ тражи да се утврди да ли је могуће добити низ у коме су сви суседни бројеви различити или не заменом два суседна или суседна елемента у низу ако је то могуће, а затим исписати „ДА ”Иначе исписати„ НЕ ”.

Пример  

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

У овом примеру можемо добити низ различитих суседних бројева заменом арр [2] и арр [3] као 5, односно 2.

Изразити суседни елементи у низуПин

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 бројева, у којем су се два од њих два пута појавила у низу, а други број се појавио једном. Дакле, чуваћемо фреквенцију сваког елемента низа. Након чувања свих фреквенција елемента. Поставит ћемо варијаблу макФрек на 0. У коју ћемо похранити максимални број фреквенција елемента, након што сазнамо максималну фреквенцију.

Због тога ћемо прелазити мапу и проверити за сваки елемент ако имамо фреквенцију већу од претходно сачуване фреквенције. Овим ћемо имати максималан број као фреквенцију и проверити да ли је та фреквенција већа од половине дужине низа. Ако је тачно, испишите НЕ, у супротном испишите ДА.

код  

Ц ++ код за разликовање суседних елемената у проблему низа

#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

Јава код за разликовање суседних елемената у проблему низа

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

Анализа сложености  

Сложеност времена

Он) где „Н“ је број елемената у низу. Будући да смо користили Хасхмап, можемо постићи линеарну временску сложеност.

Види такође
Итеративно превртање предбиљежбе

Сложеност простора

Он) где „Н“ је број елемената у низу. Како смо користили хеш-мапу, чували смо фреквенције елемената. А у најгорем случају могу бити сви различити елементи. Тада ћемо имати Н парова кључ / вредност. Дакле, имамо сложеност О (Н) простора.