אלמנטים סמוכים מובחנים במערך  


רמת קושי קַל
נשאל לעתים קרובות Coursera דה שו טיול יבמ קוליזה נגארו אופרה חדרי OYO Zoho
מערך

הצהרת בעיה  

נניח שיש לנו מספר שלם מערך. הבעיה "אלמנטים סמוכים מובחנים במערך" מבקשת לקבוע אם ניתן להשיג את המערך שבו כל המספרים הסמוכים מובחנים או לא על ידי החלפת שני אלמנטים סמוכים או שכנים במערך אם זה אפשרי ואז הדפיסו "YES "אחר להדפיס" לא ".

דוגמה  

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.

הסבר  

ניתן לנו מערך שלם. התבקשנו לקבוע אם נקבל את המערך בו האלמנטים הסמוכים המובהקים אפשריים. המשמעות היא שאם מערך כזה אינו אפשרי אז הדפיס את כן אחרת כן. כעת עלינו לבדוק כמה מספרים יש להחליף כדי לקבל את המערך הרצוי. עלינו לבדוק את המופע של כל אלמנט וגם שההתרחשות המקסימאלית לא צריכה להיות גדולה ממחצית אורך המערך. אם אורך המערך יינתן כ- 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" הוא מספר האלמנטים במערך. כפי שהשתמשנו ב- hashmap, אחסנו תדרים של אלמנטים. ובמקרה הגרוע ביותר עשויים להיות כל האלמנטים השונים. אז יהיו לנו צמדי ערך מפתח. אז יש לנו מורכבות שטח O (N).