קבוצת הופעות מרובות של אלמנטים במערך הוזמנו לפי ההתרחשות הראשונה


רמת קושי קַל
נשאל לעתים קרובות נאמן Adobe אמזון בעברית מסירה פורקיטים
מערך בליל

ניתנת לך שאלה בה נתת לא ממוין מערך עם מספר מופעים. המשימה היא לקבץ את כל המופעים המרובים של רכיבי מערך מסודרים לפי המופע הראשון. בינתיים, ההזמנה צריכה להיות זהה למספר שמגיע.

דוגמה

קלט:

[2, 3,4,3,1,3,2,4]

פלט:

[2 2 3 3 3 4 4 1]

קלט:

[5,4,1,5,4,1,5,6]

פלט:

[5 5 5 4 4 1 1 6]

אַלגוֹרִיתְם

  1. מכריזים מפת גיבוב.
  2. חצו את המערך והכניסו את כל האלמנטים ותדירותם ל- HashMap.
  3. תוך כדי חציית המערך וקבלת התדירות של כל אלמנט.
    1. הדפס את המפתח עד פעמים התדירות.
    2. הסר את arr [i] (מפתח).

הסבר להתרחשות קבוצתית של רכיבי מערך

אנו הולכים להשתמש בהאש בשבילו. Hashing מספק תכונה של אחסון האלמנטים כצמד ערך מפתח. בשאלה זו אנו נשתמש במפתח כאלמנט מערך וערך כתדר של כל אלמנט. אנחנו פשוט מכניסים את האלמנט אם הוא לא קיים בטבלת החשיש. אחרת להגדיל את ספירת (מפתח-ערך) של האלמנט.

ראשית, נכריז על HashMap שאומר "myMap". לאחר מכן אנו חוצים את כל המערך וסופרים ואוחסנים את תדר של כל אלמנט.

הבה נבחן דוגמה ונבין אותה.

דוגמה

arr = [5, 4, 1, 5, 4, 1, 5, 6]

i = 0, arr [i] = 5

myMap = {5: 1}

i = 1, arr [i] = 4

myMap = {4: 1,5: 1}

i = 2, arr [i] = 1

myMap = {1: 1,4: 1,5: 1}

i = 3, arr [i] = 5

myMap = {1: 1,4: 1,5: 2}

i = 4, arr [i] = 4

myMap = {1: 1,4: 2,5: 2}

i = 5, arr [i] = 1

myMap = {1: 2,4: 2,5: 2}

i = 6, arr [i] = 5

myMap = {1: 2,4: 2,5: 3}

i = 6, arr [i] = 6

myMap={1:2,4:2,5:3,6:1}

עכשיו יהיה לנו myMap וערכים.

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

Arr [i] = 5 תדרים = 3

5 יודפסו, שלוש פעמים, ואז נסיר את המפתח הזה ב- myMap, כך שבכל פעם שאנחנו קוראים 3 במערך הוא לא יהיה קיים ב- hashmap ולא מודפס.

Arr [i] = 4 תדרים = 2

4 יודפסו, פעמיים, המפתח יוסר ב- myMap, כך שבכל פעם שנקרא 2 במערך הוא לא יהיה קיים ב- HashMap ולא מודפס.

Arr [i] = 1 תדרים = 2

1 יודפס, פעמיים, ואז נסיר את המפתח ב- myMap, כך שבכל פעם שאנחנו קוראים 2 במערך והוא לא יהיה קיים ב- HashMap ולא מודפס.

עכשיו 5 מגיע במערך אבל זה לא יהיה קיים ב- HashMap ואותו דבר לא יקרה ולא יעשה כלום עד שיימצא האלמנט שנמצא ב- HashMap.

Arr [i] = 6 תדר = 1

6 יודפסו, פעם אחת, המפתח יוסר ב- myMap, כך שבכל פעם שאנחנו קוראים 1 במערך הוא לא יהיה קיים ב- hashmap ולא מודפס.

נקבל את התפוקה כעת כ 5 5 5 4 4 1 1 6.

יישום

תוכנית C ++ לתכנית קבוצה מרובה של רכיבי מערך הוזמנו לפי ההתרחשות הראשונה

#include<iostream>
#include<unordered_map>

using namespace std;
void arrangeInOrder(int arr[], int n)
{
    unordered_map<int, int> myMap;

    for (int i=0; i<n; i++)
    {
        myMap[arr[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        int count = myMap[arr[i]];
        for (int j=0; j<count; j++)
            cout<<arr[i]<< " ";

        myMap.erase(arr[i]);
    }
}
int main()
{
    int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    arrangeInOrder(arr,n);
    return 0;
}
10 10 10 5 3 3 4 1

תוכנית Java

import java.util.HashMap;

class multipleOccurences
{
    public static void arrangeInOrder(int arr[])
    {
        HashMap<Integer, Integer> myMap= new HashMap<Integer, Integer>();

        for (int i=0; i<arr.length; i++)
        {
            Integer current = myMap.get(arr[i]);
            if (current == null)
                current = 0;

            myMap.put(arr[i], current + 1);
        }
        for (int i=0; i<arr.length; i++)
        {
            Integer count = myMap.get(arr[i]);
            if (count != null)
            {
                for (int j=0; j<count; j++)
                {
                    System.out.print(arr[i] + " ");
                }
                myMap.remove(arr[i]);
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
        arrangeInOrder(arr);
    }
}
10 10 10 5 3 3 4 1

ניתוח מורכבות להתרחשות קבוצתית של רכיבי מערך

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך.

התייחסות