એરે એલિમેન્ટ્સના જૂથ મલ્ટીપલ ઘટના પ્રથમ ઘટના દ્વારા આદેશ આપ્યો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ભેગા એડોબ એમેઝોન દિલ્હીવારી ફોરકાઇટ્સ
અરે હેશ

તમને એક સવાલ આપવામાં આવ્યો છે જેમાં તમે એક સortedર્ટ કરેલ છે એરે સંખ્યાઓની અનેક ઘટનાઓ સાથે. કાર્ય એ છે કે એરે તત્વોની બધી બહુવિધ ઘટનાઓને પ્રથમ ઘટના દ્વારા ઓર્ડર કરવામાં આવે. દરમિયાન, ક્રમ નંબર આવે તેવો જ હોવો જોઈએ.

ઉદાહરણ

ઇનપુટ:

[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. એરેને પસાર કરો અને બધા તત્વો અને તેની આવર્તનને હેશમેપમાં મૂકો.
  3. જ્યારે એરેને ટ્રversવર્સ કરતા હો અને દરેક તત્વની આવર્તન મેળવો.
    1. તે કીને તે આવર્તન સમય સુધી છાપો.
    2. તે અરરને દૂર કરો [i] (કી).

એરે તત્વોના જૂથ મલ્ટીપલ પ્રસંગ માટે સમજૂતી

અમે તેના માટે હેશિંગનો ઉપયોગ કરીશું. હેશીંગ એ કી-વેલ્યુ જોડી તરીકે તત્વોને સ્ટોર કરવાની સુવિધા પ્રદાન કરે છે. આ પ્રશ્નમાં, આપણે એરે એલિમેન્ટ તરીકેની કી અને દરેક તત્વની આવર્તન તરીકે મૂલ્યનો ઉપયોગ કરવા જઈશું. જો તત્વો હેશ ટેબલમાં હાજર ન હોય તો અમે ફક્ત તેને શામેલ કરીએ છીએ. અન્યથા તત્વની ગણતરી (કી-મૂલ્ય) વધારો.

પ્રથમ, આપણે હેશમેપને "માય મેપ" કહેતા જાહેર કરીશું. તે પછી અમે આખા એરેને પસાર કરીએ છીએ અને ગણતરી અને સ્ટોર કરીએ છીએ આવર્તન દરેક તત્વ છે.

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ અને તેને સમજીએ.

ઉદાહરણ

એઆર = [5, 4, 1, 5, 4, 1, 5, 6]

i = 0, એરે [i] = 5

માયમેપ = {5: 1}

i = 1, એરે [i] = 4

માયમેપ = {4: 1,5: 1}

i = 2, એરે [i] = 1

માયમેપ = {1: 1,4: 1,5: 1}

i = 3, એરે [i] = 5

માયમેપ = {1: 1,4: 1,5: 2}

i = 4, એરે [i] = 4

માયમેપ = {1: 1,4: 2,5: 2}

i = 5, એરે [i] = 1

માયમેપ = {1: 2,4: 2,5: 2}

i = 6, એરે [i] = 5

માયમેપ = {1: 2,4: 2,5: 3}

i = 6, એરે [i] = 6

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

હવે આપણી પાસે માયમેપ અને તેમાં મૂલ્યો હશે.

એરેમાં ઓર્ડર થયેલ તત્વ સાથે ફરીથી એરેને ટ્રversસ કર્યા પછી આપણને આવર્તન મળશે. દરેક અરે તત્વને તેની આવર્તન સાથે લેવું અને તે આવર્તન સમય સુધી લૂપ બનાવવું અને આવર્તન સમય સુધી બધા એરે તત્વો છાપવા પછી તે એરે કીને કા removeી નાખો જેથી તે આગળના ટ્ર traવર્સેલમાં ફરીથી છાપશે નહીં.

અરર [i] = 5 આવર્તન = 3

5 છાપવામાં આવશે, 3 વખત, પછી અમે તે કીને માયમેપમાં દૂર કરીશું, તેથી જ્યારે પણ આપણે એરેમાં 5 વાંચીએ છીએ, તે હેશમેપમાં હાજર રહેશે નહીં અને છાપશે નહીં.

અરર [i] = 4 આવર્તન = 2

4 છાપવામાં આવશે, 2 વાર, કી મારામેપમાં દૂર કરવામાં આવશે, તેથી જ્યારે પણ આપણે એરેમાં 4 વાંચીએ છીએ, તે હેશમેપમાં હાજર રહેશે નહીં અને છાપશે નહીં.

અરર [i] = 1 આવર્તન = 2

1 છાપવામાં આવશે, 2 વખત, પછી આપણે તે કીને માયમેપમાં દૂર કરીશું, તેથી જ્યારે પણ આપણે એરેમાં 5 વાંચીએ અને તે હેશમેપમાં હાજર રહેશે નહીં અને છાપશે નહીં.

હવે 5 એરેમાં આવે છે પરંતુ તે હેશમેપમાં હાજર રહેશે નહીં અને તે જ થાય છે અને જ્યાં સુધી એલિમેન્ટ ન મળે ત્યાં સુધી કંઈ નહીં કરો જે હેશમેપમાં હાજર છે.

અરર [i] = 6 આવર્તન = 1

6 છાપવામાં આવશે, 1 વખત, કી મારામેપમાં દૂર કરવામાં આવશે, તેથી જ્યારે પણ આપણે એરેમાં 4 વાંચીએ છીએ, તે હેશમેપમાં હાજર રહેશે નહીં અને છાપશે નહીં.

હવે આપણી પાસે આઉટપુટ 5 5 5 4 4 1 1 6 હશે.

અમલીકરણ

પ્રથમ ઘટના દ્વારા આદેશિત એરે તત્વોના જૂથ મલ્ટીપલ પ્રસંગ માટે સી ++ પ્રોગ્રામ

#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

જાવા પ્રોગ્રામ

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

એરે તત્વોના જૂથ મલ્ટીપલ ઘટના માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

સંદર્ભ