আসল অ্যারের মতো মোট পৃথক পৃথক উপাদান থাকা সাবহারিকে গণনা করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ডেটাব্রিক্স প্রভূত Honeywell Payu বর্গক্ষেত্র তেরদাটা ইয়ানডেক্স
বিন্যাস কাটা হ্যাশ সহচরী উইন্ডোতে

সমস্যা বিবৃতি

"আসল হিসাবে মোট পৃথক পৃথক উপাদান থাকা সাবহারিকে গণনা করুন বিন্যাস”বলে যে আপনাকে একটি পূর্ণসংখ্যার অ্যারে দেওয়া হবে। সমস্যা বিবৃতিতে উপ-অ্যারেগুলির মোট সংখ্যা জানতে জিজ্ঞাসা করা হয়েছে যাতে একটি মূল অ্যারেতে উপস্থিত সমস্ত স্বতন্ত্র উপাদান রয়েছে।

উদাহরণ

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 , 2 এ মূল অ্যারে হিসাবে সমস্ত স্বতন্ত্র উপাদান রয়েছে।

মূল অ্যারে হিসাবে মোট পৃথক পৃথক উপাদান থাকা সাবারিগুলিকে গণনা করার জন্য অ্যালগরিদম

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 থেকে শুরু করে আমরা আবার একটি সাব-অ্যারের সন্ধানে একটি লুপে প্রবেশ করব, যখন ডানটি n এর চেয়ে কম এবং ম্যাক্সা কে থেকে কম হবে। এখন, আমরা অ্যারে উপাদানটি রাখব এবং এর ফ্রিকোয়েন্সিটি 1 দ্বারা বাড়িয়ে দেব আমরা বর্তমান উপাদানটির 1 টি ফ্রিকোয়েন্সি আছে কিনা তা যাচাই করব বা এটি ঠিক হিসাবে পাওয়া যায় তবে আমরা এটির আরও কিছুতে এটি আপডেট করেছি ম্যাক্সা

বাইরে আসার পরে লুপ করার সময়, আপনার কাছে ম্যাক্সসার একটি বর্ধিত মান থাকবে, যদি এটি কে এর সমান হয় তবে আউটপুটটিকে n-ডান +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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা অ্যারেটি অতিক্রম করেছি এবং হ্যাশম্যাপ ব্যবহার করেছি যা আমাদের রৈখিক সময়ের জটিলতা অর্জন করে।

স্পেস জটিলতা ity

চালু) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। কারণ আমরা ইনপুট সংরক্ষণ করতে একটি অ্যারে এবং একটি হ্যাশম্যাপ ব্যবহার করেছি যা এন উপাদানগুলিকে সঞ্চয় করতে চলেছে। সুতরাং লিনিয়ার স্পেস জটিলতা অর্জিত হয়।