मूळ अ‍ॅरेसारखे एकूण भिन्न घटक असलेली सबर्रे मोजा


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

समस्या विधान

“मूळ प्रमाणे एकूण भिन्न घटक असलेली उपनगरे मोजा अॅरे”असे सांगते की तुम्हाला पूर्णांक अ‍ॅरे देण्यात आला आहे. समस्येचे विधान मूळ अ‍ॅरेमध्ये उपस्थित असलेल्या सर्व भिन्न घटक असलेल्या उप-अ‍ॅरेची एकूण संख्या शोधण्यास सांगते.

उदाहरण

arr[] = {2, 1, 3, 2, 3}
5

स्पष्टीकरणः उप-अ‍ॅरे ⇒ {2, 1, 3}, {1, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 2} आणि {2, 1, 3, 2 , 3 original मध्ये मूळ अ‍ॅरे म्हणून सर्व भिन्न घटक असतात.

मूळ अ‍ॅरेसारखे एकूण भिन्न घटक असलेली सबर्रे मोजा

arr[] = {2, 4, 3, 4, 1, 2}
4

स्पष्टीकरणः उप-अ‍ॅरे ⇒ {3, 4, 1, 2}, {4, 3, 4, 1, 2}, {2, 4, 3, 4, 1} आणि {2, 4, 3, 4, 1 , २ मध्ये मूळ अ‍ॅरे म्हणून सर्व भिन्न घटक असतात.

मूळ अ‍ॅरे प्रमाणे एकूण भिन्न घटक असलेली सबरीची गणना करण्यासाठी अल्गोरिदम

1. Declare a map.
2. Add all the values of array into the map with 1 as each key’s value.
3. Find the size of the map, store it to k and clear the map.
4, Set output, right, and maxsa to 0.
5. Traverse the array, from i=0, to i < n(length of the array).
  1. While the right is less than n and maxsa is less than k,
    1. Insert arr[right] and increase its frequency by 1.
    2. Check if the map’s value of current array element (arr[right]) is equal to 1 if true then increase the count of maxsa by 1.
  2. Increase the count of right by 1.
  3. If maxsa is equal to k, then update output à output += (n - right + 1).
  4. Insert the value of current arr[left] and decrease its frequency by 1.
  5. If the map’s arr[left] is equal to 0, then decrease the value of maxsa by 1.
6. Return output.

स्पष्टीकरण

आम्ही एक दिले आहे पूर्णांक अ‍ॅरे, आम्हाला मूळ अ‍ॅरेमध्ये उपस्थित असलेल्या सर्व भिन्न घटक असलेल्या उप-अ‍ॅरेची एकूण संख्या शोधण्यास सांगितले जाते. यासाठी आम्ही वापरू हॅशिंग. हा कोड सोडविण्यासाठी कार्यक्षम दृष्टीकोन आहे.

घोषित ए नकाशा. आम्ही संपूर्ण अ‍ॅरे पार करणार आहोत आणि प्रत्येक घटकास फक्त 1 च्या वारंवारतेसह नकाशामध्ये ठेवू. कारण आम्हाला प्रत्येक घटकाची वारंवारता मोजण्याची इच्छा नाही. दिलेल्या अ‍ॅरेमध्ये किती अद्वितीय की उपस्थित आहेत हे जाणून घेण्यासाठीच हे आहे. आम्ही व्हेरिएबल के मध्ये नकाशाचा आकार साठवू आणि नकाशा साफ करू.

आम्ही संपूर्ण अ‍ॅरे पुढे करणार आहोत. परंतु त्यापूर्वी आपण आउटपुट, राइट आणि मॅक्ससाचे मूल्य 0 वर सेट केले. 0 पासून प्रारंभ करून आपण पुन्हा सब-अ‍ॅरेच्या शोधात लूपमध्ये प्रवेश करू, तर उजवा एनपेक्षा कमी आणि मॅक्ससा के पेक्षा कमी असेल. आता आपण अ‍ॅरे एलिमेंटस ठेवू आणि त्याची वारंवारता १ ने वाढवू. सध्याच्या घटकाची वारंवारता १ आहे का ते तपासू. किंवा जर ते खरे असल्याचे आढळले तर आम्ही त्यास त्यास अजून अद्ययावत केले, तर व्हॅल्यू वाढवा. मॅक्सेचा

च्या बाहेर आल्यानंतर पळवाट असताना, आपल्याकडे मॅक्साचे वर्धित मूल्य असेल, जर ते के बरोबर असेल तर आउटपुट एन-राइट +1 वर अद्यतनित करा. जसे आपण आधीच अ‍ॅरे एलिमेंटसची व्हॅल्यू नकाशामध्ये ठेवली आहेत. आता आम्ही त्याची वारंवारता 1 ने कमी करू आणि अरर [डावीकडे] मूल्य 0 च्या बरोबर असल्याचे तपासू आणि मॅक्ससा मूल्य कमी करू. जेव्हा आम्हाला मॅक्ससा टू के चे मूल्य सापडेल तेव्हा आउटपुट व्हॅल्यू अपडेट करू.

कोड

मूळ अ‍ॅरेसारखे एकूण भिन्न घटक असलेल्या सबर्रेची गणना करण्यासाठी सी ++ कोड

#include<iostream>
#include<unordered_map>

using namespace std;

int getSubArrayDistinct(int arr[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[arr[i]] = 1;

    int k = MAP.size();

    MAP.clear();

    int output = 0, right = 0, maxsa = 0;
    for (int left = 0; left < n; ++left)
    {
        while (right < n && maxsa < k)
        {
            ++MAP[ arr[right] ];

            if (MAP[ arr[right] ] == 1)
                ++maxsa;

            ++right;
        }
        if (maxsa == k)
        {
            output += (n - right + 1);
        }
        --MAP[ arr[left] ];

        if (MAP[ arr[left] ] == 0)
        {
            --maxsa;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 1, 3, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getSubArrayDistinct(arr, n);
}
5

मूळ अ‍ॅरेसारखे एकूण भिन्न घटक असलेल्या सबर्रे मोजण्यासाठी जावा कोड

import java.util.HashMap;

class SubarrayWithDistinctEle
{
    public static int getSubArrayDistinct(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>()
        {
            @Override
            public Integer get(Object key)
            {
                if(!containsKey(key))
                    return 0;
                return super.get(key);
            }
        };

        for (int i = 0; i < n; ++i)
            MAP.put(arr[i], 1);
        int k = MAP.size();

        MAP.clear();

        int output = 0, right = 0, maxsa = 0;
        for (int left = 0; left < n; ++left)
        {
            while (right < n && maxsa < k)
            {
                MAP.put(arr[right], MAP.get(arr[right]) + 1);

                if (MAP.get(arr[right])== 1)
                {
                    ++maxsa;
                }

                ++right;
            }
            if (maxsa == k)
            {
                output += (n - right + 1);
            }

            MAP.put(arr[left], MAP.get(arr[left]) - 1);

            if (MAP.get(arr[left]) == 0)
                --maxsa;
        }
        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2, 1, 3, 2, 3};
        int n=arr.length;
        System.out.println(getSubArrayDistinct(arr, n));
    }
}
5

गुंतागुंत विश्लेषण

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

ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही अ‍ॅरेला मागे टाकले आहे आणि हॅशमॅप वापरला आहे ज्यामुळे आम्हाला रेखीय वेळ गुंतागुंत प्राप्त झाली.

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

ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. कारण आपण इनपुट संग्रहित करण्यासाठी अ‍ॅरे आणि हॅशमॅप वापरला आहे जे एन एलिमेंट्स साठवणार आहे. अशा प्रकारे रेखीय अवकाशातील अवघडपणा प्राप्त होतो.