العناصر المتجاورة المميزة في المصفوفة


مستوى الصعوبة سهل
كثيرا ما يطلب في Coursera دي شو رفع IBM كوليزا ناجارو العمل غرف OYO زوهو
مجموعة

المشكلة بيان

افترض أن لدينا ملف عدد صحيح مجموعة. تطلب مشكلة "العناصر المتجاورة المميزة في المصفوفة" تحديد ما إذا كان من الممكن الحصول على المصفوفة التي تكون فيها جميع الأرقام المجاورة مميزة أم لا عن طريق تبديل عنصرين متجاورين أو متجاورين في مصفوفة إذا كان ذلك ممكنًا ، ثم اطبع "نعم" "آخر طباعة" لا ".

مثال

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 بطباعة YES. الآن ، نحتاج إلى التحقق من عدد الأرقام المراد تبديلها للحصول على المصفوفة المطلوبة. نحتاج إلى التحقق من حدوث كل عنصر وأيضًا أن الحد الأقصى للتواجد لا ينبغي أن يكون أكبر من نصف طول المصفوفة. إذا كان طول المصفوفة هو 5. إذا كان للعنصر 3 تكرارات في المصفوفة. بعد ذلك سيكون من الممكن إعادة ترتيب المصفوفة في الموضع الأول والثالث والخامس. لذلك سيكون من الممكن الحصول على عناصر متجاورة مميزة في المصفوفة.

سنفعله هو أن نعلن أ رسم خريطة. سنقوم بعد ذلك باجتياز المصفوفة وإحصاء تكرار كل عنصر. قم بتخزين جميع ترددات كل عنصر في الخريطة في نفس الوقت. لنفترض أن لدينا مصفوفة من 5 أرقام ، حدث فيها اثنان منها مرتين في مصفوفة وحدث رقم آخر مرة واحدة. لذلك سنقوم بتخزين تردد كل عنصر من عناصر المصفوفة. بعد تخزين جميع ترددات العنصر. سنقوم بتعيين متغير maxFreq على 0. حيث سنقوم بتخزين الحد الأقصى لعدد التردد لعنصر ما ، بعد معرفة الحد الأقصى للتردد.

لذلك ، سوف نجتاز الخريطة ، ونتحقق من كل عنصر ، إذا كان لدينا تردد أكبر من التردد المخزن مسبقًا. مع هذا ، سيكون لدينا الحد الأقصى لعدد الترددات ، والتحقق مما إذا كان هذا التردد أكبر من نصف طول المصفوفة. إذا كان هذا صحيحًا ، فقم بطباعة NO ، وإلا اطبع YES.

رمز

كود 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 (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأننا استخدمنا Hashmap ، فإننا قادرون على تحقيق تعقيد زمني خطي.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. كما استخدمنا hashmap ، كنا نخزن ترددات العناصر. وفي أسوأ الأحوال ، قد تكون هناك عناصر مختلفة. ثم سيكون لدينا أزواج N الرئيسية والقيمة. إذن لدينا تعقيد فضاء O (N).