גרופּע קייפל פּאַסירונג פון ערייז עלעמענטן אָרדערד דורך ערשטער פּאַסירונג  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַקקאָליטע אַדאָובי אַמאַזאָן דעליווערי פאָורקיטעס
מענגע האַש

איר באַקומען אַ קשיא אין וואָס איר האָט געגעבן אַ ונסאָרטעד מענגע מיט קייפל פֿאַלן פון נומערן. די אַרבעט איז צו גרופּע אַלע קייפל פֿאַלן פון מענגע עלעמענטן באפוילן דורך ערשטער פּאַסירונג. דערווייַל, דער סדר זאָל זיין די זעלבע ווי די נומער קומט.

בייַשפּיל  

ינפּוט:

[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. אַראָפּנעמען אַז אַרר [i] (שליסל).

דערקלערונג פֿאַר מער ווי איין גרופע עריי עלעמענטן  

מיר וועלן נוצן האַשינג פֿאַר אים. כאַשינג גיט אַ שטריך פון סטאָרינג די עלעמענטן ווי אַ שליסל-ווערט פּאָר. אין דעם קשיא, מיר וועלן נוצן אַ שליסל ווי אַ מענגע עלעמענט און אַ ווערט ווי אַ אָפטקייַט פון יעדער עלעמענט. מיר פשוט שטעלן דעם עלעמענט אויב עס איז נישט פאָרשטעלן אין די האַש טיש. אַנדערש פאַרגרעסערן די ציילן (שליסל-ווערט) פון די עלעמענט.

ערשטער, מיר וועלן דערקלערן אַ HashMap זאָגן "מימאַפּ". מיר דורכפאָר די גאנצע מענגע און קאַונטינג און סטאָרד די אָפטקייַט פון יעדער עלעמענט.

זאל אונדז באַטראַכטן אַ בייַשפּיל און פֿאַרשטיין עס.

בייַשפּיל

אַרר = [5, 4, 1, 5, 4, 1, 5, 6]

זע אויך
געפֿינען סובאַרראַי מיט אַ געגעבן סכום (האַנדלעס נעגאַטיוו נומערן)

איך = 0, אַרר [איך] = 5

myMap = {5: 1}

איך = 1, אַרר [איך] = 4

myMap = {4: 1,5: 1}

איך = 2, אַרר [איך] = 1

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

איך = 3, אַרר [איך] = 5

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

איך = 4, אַרר [איך] = 4

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

איך = 5, אַרר [איך] = 1

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

איך = 6, אַרר [איך] = 5

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

איך = 6, אַרר [איך] = 6

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

איצט מיר וועלן האָבן אַ מיימאַפּ און וואַלועס.

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

אַרר [איך] = 5 אָפטקייַט = 3

5 וועט ווערן געדרוקט, 3 מאָל, און מיר וועלן באַזייַטיקן דעם שליסל אין מימאַפּ, אַזוי ווען מיר לייענען 5 אין אַ מענגע, עס איז נישט פאָרשטעלן אין האַשמאַפּ און קען נישט דרוקן.

אַרר [איך] = 4 אָפטקייַט = 2

4 וועט ווערן געדרוקט, 2 מאָל, דער שליסל וועט ווערן אַוועקגענומען אין myMap, אַזוי ווען מיר לייענען 4 אין אַ מענגע, עס איז נישט פאָרשטעלן אין HashMap און קען נישט דרוקן.

אַרר [איך] = 1 אָפטקייַט = 2

1 וועט ווערן געדרוקט, 2 מאָל, און מיר וועלן באַזייַטיקן דעם שליסל אין myMap, אַזוי ווען מיר לייענען 5 אין אַ מענגע און עס וועט נישט זיין פאָרשטעלן אין HashMap און קען נישט דרוקן.

איצט 5 קומט אין מענגע, אָבער עס וועט נישט זיין פאָרשטעלן אין HashMap און די זעלבע כאַפּאַנז און טאָן גאָרנישט ביז דער עלעמענט איז געפֿונען וואָס איז פאָרשטעלן אין HashMap.

אַרר [איך] = 6 אָפטקייַט = 1

6 וועט ווערן געדרוקט, איין מאָל, דער שליסל וועט ווערן אַוועקגענומען אין myMap, אַזוי ווען מיר לייענען 1 אין די מענגע, עס איז נישט פאָרשטעלן אין hashmap און קען נישט דרוקן.

די פּראָדוקציע איז איצט 5 5 5 4 4 1 1.

ימפּלעמענטאַטיאָן  

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גרופע קייפל פון עריי עלעמענטן  

צייט קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

זע אויך
קאָמבינאַציע סאַם לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

דערמאָנען