प्रथम घटनेद्वारे क्रमित अ‍ॅरे एलिमेंट्सचा गट मल्टिपल प्रसंग


अडचण पातळी सोपे
वारंवार विचारले एकत्रित अडोब ऍमेझॉन दिल्लीवारी फोरकाइट्स
अरे हॅश

आपणास एक प्रश्न देण्यात आला आहे ज्यामध्ये आपण एक विवादास्पद दिला आहे अॅरे संख्या अनेक घटनांसह. प्रथम घटनेद्वारे क्रमवारी लावलेल्या अ‍ॅरे घटकांच्या सर्व घटनांचे गटबद्ध करणे हे कार्य आहे. दरम्यान, ऑर्डर आल्याप्रमाणेच असावी.

उदाहरण

इनपुट:

[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. अ‍ॅरेचा शोध घेताना आणि प्रत्येक घटकाची वारंवारता मिळवा.
    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}

आता त्यात मायमॅप आणि व्हॅल्यूज असतील.

अ‍ॅरेमध्ये ऑर्डर केलेल्या घटकासह अ‍ॅरेचा शोध घेतल्यानंतर आपल्याला वारंवारता मिळेल. प्रत्येक अ‍ॅरे घटक त्याच्या वारंवारतेसह घेतो आणि त्या वारंवारतेच्या वेळेपर्यंत पळवाट बनविते आणि वारंवारतेच्या वेळेपर्यंत सर्व अ‍ॅरे घटक मुद्रित केल्यानंतर ती अ‍ॅरे की काढून टाकते जेणेकरून ते पुढील ट्रॉव्हर्सलमध्ये पुन्हा मुद्रित होणार नाही.

अरे [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

अ‍ॅरे घटकांच्या एकाधिक घटनांसाठी जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

संदर्भ