Жалпы жиынтық элементтері бар ішкі жиымдарды санаңыз


Күрделілік дәрежесі орта
Жиі кіреді Amazon Мәліметтер базасы Фаб Honeywell PayU шаршы Терадата Яндекс
Array Hash Хэш Сырғымалы терезе

Проблемалық мәлімдеме

«Жалпы элементтері түпнұсқамен бірдей субарларды санаңыз массив»Сізге бүтін массив берілгенін айтады. Проблемалық шешім түпнұсқа массивтегі барлық әртүрлі элементтерден тұратын ішкі жиымдардың жалпы санын білуді сұрайды.

мысал

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.

Түсіндіру

Біз ан бүтін сан массив, бізде бастапқы массивтегі барлық әртүрлі элементтері бар ішкі жиымдардың жалпы санын білу сұралады. Ол үшін біз қолданамыз Хэш. Бұл кодты шешудің тиімді тәсілі.

Декларация а карта. Біз бүкіл массивті айналып өтіп, картаға әр элементті тек 1 жиілігімен енгіземіз, өйткені біз әр элементтің жиілігін санағымыз келмейді. Бұл берілген массивте қанша ерекше кілт бар екенін білу үшін ғана қажет. Біз картаның өлшемін k айнымалысына сақтаймыз және картаны тазалаймыз.

Біз бүкіл массивті айналып өтеміз. Бірақ бұған дейін шығыс, оң және макса мәндерін 0-ге қойдық, 0-ден бастап, қайтадан ішкі жиымды іздеп, циклға кіреміз, ал оң жағы n-ден, ал maxsa k-ден аз. Енді массив элементін қойып, оның жиілігін 1-ге көбейтеміз. Ағымдағы элементтің жиілігі 1 болатындығын тексереміз. Немесе біз оны жай ғана жаңартып алдық, егер ол рас болса, онда мәнді көбейтеміз maxsa.

Шыққаннан кейін while цикл, сізде maxsa өсетін мәні болады, егер ол k-ге тең болса, онда n-right +1 мәніне жаңартыңыз. Массив элементінің мәндерін картаға енгізгендіктен. Енді біз оның жиілігін 1-ге азайтамыз және arr [сол жақ] мәні 0-ге тең екендігін тексеріп, maxsa мәнін төмендетеміз. Maxsa мәнін k-ге дейін тапқан сайын шығыс мәнін жаңартып отырамыз.

код

С ++ коды, бастапқы массивпен бірдей жалпы элементтері бар ішкі жиымдарды санауға арналған

#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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз массивтен өтіп, HashMap-ді қолданғандықтан, бұл уақыттың сызықтық күрделілігіне қол жеткізді.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз енгізуді сақтау үшін массив пен N элементтерін сақтайтын HashMap қолдандық. Осылайша ғарыштық сызықтық күрделілікке қол жеткізіледі.