عد المصفوفات الفرعية التي تحتوي على إجمالي عناصر مميزة مثل المصفوفة الأصلية


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Databricks القوات المسلحة البوروندية هانيويل 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} تحتوي على جميع العناصر المميزة كمصفوفة أصلية.

عد المصفوفات الفرعية التي تحتوي على إجمالي عناصر مميزة مثل المصفوفة الأصلية

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.

تفسير

لقد قدمنا عدد صحيح المصفوفة ، يُطلب منا معرفة العدد الإجمالي للمصفوفات الفرعية التي تحتوي على جميع العناصر المميزة الموجودة في المصفوفة الأصلية. لهذا سوف نستخدم تجزئة. إنها طريقة فعالة لحل هذا الرمز.

تعلن أ رسم خريطة. سنقوم باجتياز المصفوفة بأكملها ، ووضع كل عنصر في الخريطة بتردد واحد فقط. لأننا لا نريد حساب تكرار كل عنصر. هذا فقط لمعرفة عدد المفاتيح الفريدة الموجودة في مصفوفة معينة. سنخزن حجم الخريطة في المتغير k ومسح الخريطة.

سنقوم باجتياز المصفوفة بأكملها. لكن قبل ذلك ، قمنا بتعيين قيمة المخرجات ، right و maxsa إلى 0. بدءًا من 0 ، سندخل مرة أخرى في حلقة بحثًا عن مصفوفة فرعية ، بينما يكون اليمين أقل من n و maxsa أقل من k. الآن ، سوف نضع عنصر المصفوفة ونزيد تردده بمقدار 1. سوف نتحقق مما إذا كان العنصر الحالي له تردد 1. أو قمنا بتحديثه إلى المزيد من ذلك ، إذا تبين أنه صحيح ، فقم بزيادة القيمة من maxsa.

بعد الخروج من حائط اللوب، ستحصل على قيمة متزايدة لـ maxsa ، إذا كانت تساوي k ، فقم بتحديث الإخراج إلى n-right +1. كما وضعنا بالفعل قيم عنصر المصفوفة في الخريطة. سنقوم الآن بتقليل تردده بمقدار 1 ، والتحقق مما إذا كانت قيمة arr [اليسرى] تساوي 0 وتقليل قيمة maxsa. كلما وجدنا قيمة maxsa إلى 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

كود Java لحساب المصفوفات الفرعية التي تحتوي على إجمالي عناصر مميزة مثل المصفوفة الأصلية

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

تحليل التعقيد

تعقيد الوقت

على) أين "N" هو عدد العناصر في المصفوفة. نظرًا لأننا اجتزنا المصفوفة واستخدمنا HashMap مما جعلنا نحقق تعقيدًا زمنيًا خطيًا.

تعقيد الفضاء

على) أين "N" هو عدد العناصر في المصفوفة. لأننا استخدمنا مصفوفة لتخزين المدخلات و HashMap الذي سيخزن عناصر N. وهكذا يتحقق تعقيد الفضاء الخطي.