کل الگ الگ عنصر رکھنے والی سبریوں کی گنتی کریں جو اصل صف کی طرح ہیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ڈیٹا بکس فیب ہنیویل پی پی یو چوک ٹیراداٹا Yandex
لڑی ہیش ہیکنگ سلائیڈنگ ونڈو

مسئلہ یہ بیان

“اصل کے جیسے کل الگ الگ عنصر رکھنے والی سبریوں کی گنتی کریں صف”بیان کرتا ہے کہ آپ کو ایک انٹیجر سرنی دی جاتی ہے۔ مسئلہ بیان میں ذیلی صفوں کی کل تعداد معلوم کرنے کے لئے کہا گیا ہے جس میں تمام الگ عنصر شامل ہیں جیسے ایک اصل صف میں موجود ہیں۔

مثال کے طور پر

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 میں اصل صف کے بطور تمام الگ عناصر شامل ہیں۔

کل الگ الگ عنصر رکھنے والی سبریوں کی گنتی کریں جو اصل صف کی طرح ہیں

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.

وضاحت

ہم نے ایک دیا ہے عددی صف ، ہم سے ذیلی صفوں کی کل تعداد معلوم کرنے کے لئے کہا گیا ہے جس میں تمام الگ عناصر پر مشتمل ہے جیسے ایک اصل صف میں موجود ہے۔ اس کے لئے ، ہم استعمال کریں گے ہیکنگ. اس کوڈ کو حل کرنے کے ل It یہ ایک موثر نقطہ نظر ہے۔

اعلان a نقشہ. ہم پوری صف کو عبور کرنے جارہے ہیں ، اور ہر عنصر کو صرف ایک تعدد کے ساتھ نقشے میں ڈال رہے ہیں جو 1 ہے۔ کیونکہ ہم ہر عنصر کی تعدد کو گننا نہیں چاہتے ہیں۔ یہ صرف یہ جاننے کے لئے ہے کہ ایک دیئے گئے صف میں کتنی منفرد کنجی موجود ہیں۔ ہم نقشے کے سائز کو متغیر k میں محفوظ کریں گے اور نقشہ کو صاف کریں گے۔

ہم پوری صف کو عبور کرنے جارہے ہیں۔ لیکن اس سے پہلے ، ہم آؤٹ پٹ ، دائیں اور مکسسا کی قیمت 0 پر مقرر کرتے ہیں ، 0 سے شروع ہوکر ، ہم ایک ذیلی سرنی کی تلاش میں ایک لوپ میں دوبارہ داخل ہوں گے ، جبکہ دائیں ن سے کم اور میکسا K سے کم ہے۔ اب ، ہم صف عنصر ڈالیں گے اور اس کی تعدد کو 1 سے بڑھا دیں گے۔ ہم جانچیں گے کہ موجودہ عنصر کی فریکوئنسی 1 ہے۔ یا ہم نے ابھی اسے اس سے کہیں زیادہ تازہ کردیا ، اگر یہ صحیح پایا جاتا ہے تو ، قدر میں اضافہ کریں مکسا کی

کے باہر آنے کے بعد جبکہ لوپ، آپ کے پاس میکسا کی بڑھتی ہوئی قیمت ہوگی ، اگر یہ k کے برابر ہے ، تو آؤٹ پٹ کو n-right +1 پر اپ ڈیٹ کریں۔ جیسا کہ ہم نقشہ میں سرنی عنصر کی اقدار کو پہلے ہی ڈال چکے ہیں۔ اب ہم اس کی تعدد کو 1 سے کم کردیں گے ، اور جانچ کریں گے کہ آیا [بائیں] قدر 0 کے برابر ہے اور میکسا کی قدر میں کمی آئے گی۔ جب بھی ہمیں میکسا سے k کی قدر ملتی ہے ہم آؤٹ پٹ ویلیو کو اپ ڈیٹ کرتے ہیں۔

ضابطے

C ++ کوڈ جس میں سبیریوں کی گنتی کرنے کے لئے کل صفر کے مختلف عنصر ہیں جو اصل صف کے برابر ہیں

#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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) کہاں "N" صف میں عناصر کی تعداد ہے۔ چونکہ ہم صف کو عبور کرتے ہیں اور ہاش میپ کا استعمال کرتے ہیں جس کی وجہ سے ہمیں لائن ٹائم پیچیدگی حاصل ہوتی ہے۔

خلائی پیچیدگی

O (N) کہاں "N" صف میں عناصر کی تعداد ہے۔ کیونکہ ہم نے ان پٹ اور ہش میپ کو ذخیرہ کرنے کے لئے ایک صف کا استعمال کیا ہے جو N عناصر کو ذخیرہ کرنے جارہا ہے۔ اس طرح لکیری اسپیس پیچیدگی حاصل ہوجاتی ہے۔