Различни съседни елементи в масив  


Ниво на трудност Лесно
Често задавани в Coursera DE Шоу Екскурзия IBM Кулиза Нагаро опера OYO Стаи Zoho
Array

Декларация за проблема  

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

Пример  

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

В този пример можем да получим масива от различни съседни числа, като заменим arr [2] и arr [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.

Обяснение  

Получава се целочислен масив. Ние бяхме помолени да определим дали получаваме масива, в който са възможни отделните съседни елементи. Това означава, че ако такъв масив не е възможен, отпечатайте NO else print YES. Сега трябва да проверим колко числа трябва да бъдат разменени, за да получим желания масив. Трябва да проверим появата на всеки елемент и също така, че максималната поява не трябва да бъде по-голяма от половината от дължината на масива. Ако дължината на масив ще бъде дадена като 5. Ако елемент има 3 повторения в масив. Тогава ще бъде възможно пренареждането на масива на първа, трета и пета позиция. Така че би било възможно да се получат различни съседни елементи в масив.

Вижте също
Намерете сортирана подпоследователност с размер 3 за линейно време

Ние ще направим е да декларираме a карта. След това ще преминем през масива и ще преброим честотата на всеки елемент. Едновременно съхранявайте всички честоти на всеки елемент в карта. Да предположим, че имаме масив от 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

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

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

О (п) където "н" е броят на елементите в масива. Тъй като използвахме Hashmap, можем да постигнем линейна сложност във времето.

Вижте също
Итеративно обръщане на предварителна поръчка

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

О (п) където "н" е броят на елементите в масива. Тъй като използвахме hashmap, съхранявахме честоти на елементи. И в най-лошия случай може да има различни елементи. Тогава ще имаме N двойки ключ-стойност. Така че имаме O (N) космическа сложност.