عناصر مجاور مجزا در یک آرایه


سطح دشواری ساده
اغلب در Coursera دی شاو پیاده روی آی بی ام کولیزا ناگارو اپرا اتاق های OYO ZOHO
صف

بیان مسأله

فرض کنید ما یک عدد صحیح صف. مسئله "عناصر مجاور مجزا در یک آرایه" می خواهد تعیین کند که آیا می توان آرایه ای را که در آن تمام اعداد مجاور متمایز هستند بدست آورد یا نه با تعویض دو عنصر مجاور یا همسایه در یک آرایه در صورت امکان ، سپس چاپ "بله" "دیگری چاپ" نه ".

مثال

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 NO را بله چاپ کنید. اکنون ، باید بررسی کنیم که چند عدد قرار است عوض شوند تا آرایه مورد نظر را بدست آوریم. ما باید وقوع هر عنصر را بررسی کنیم و همچنین حداکثر میزان وقوع نباید بیش از نیمی از طول آرایه باشد. اگر طول یک آرایه به عنوان 5 داده شود. اگر یک عنصر 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

کد جاوا برای عناصر مجاور مجزا در یک مسئله آرایه

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) هستیم.