Падлічваць падмасівы, якія маюць агульную колькасць розных элементаў, аднолькавых з арыгінальным масівам  


Узровень складанасці серада
Часта пытаюцца ў амазонка Збор дадзеных Fab Honeywell PayU Плошча Teradata Яндэкс
масіў гашыш хэшавання Рассоўнае акно

Пастаноўка праблемы  

«Падлічваць падмасівы, якія маюць розныя асобныя элементы, такія ж, як і арыгінал масіў”Сцвярджае, што вам дадзены цэлалікавы масіў. Пастаноўка праблемы просіць высветліць агульную колькасць падмасіваў, якія ўтрымліваюць усе розныя элементы, якія прысутнічаюць у зыходным масіве.

Прыклад  

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} ўтрымліваюць усе розныя элементы ў выглядзе арыгінальнага масіва.

Падлічваць падмасівы, якія маюць агульную колькасць розных элементаў, аднолькавых з арыгінальным масівамPin

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 сімвалаў

Абвясціце а карта. Мы збіраемся прайсці ўвесь масіў і ўнесці кожны элемент у карту толькі з частатой, якая роўная 1. Паколькі мы не хочам лічыць частату кожнага элемента. Гэта проста для таго, каб даведацца, колькі унікальных ключоў прысутнічае ў дадзеным масіве. Мы захаваем памер карты ў зменнай k і ачысцім карту.

Мы збіраемся прайсці ўвесь масіў. Але перад гэтым мы ўсталёўваем значэнне вываду, справа і maxsa на 0. Пачынаючы з 0, мы зноў увойдзем у цыкл у пошуках падмасіва, у той час як справа менш за n, а maxsa менш за k. Зараз мы паставім элемент масіва і павялічым яго частату на 1. Мы праверым, ці ёсць у бягучага элемента частата 1. Ці мы проста абнавілі яго больш, калі ён будзе ісцінай, павялічце значэнне з макссы.

Пасля выхаду з у той час як цыкл, у вас будзе павялічанае значэнне maxsa, калі яно роўна k, то абнавіце вывад на n-справа +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

Аналіз складанасці  

Складанасць часу

O (N) дзе "N" - колькасць элементаў у масіве. Так як мы прайшлі масіў і выкарысталі HashMap, што прымусіла нас дасягнуць лінейнай складанасці ў часе.

Глядзіце таксама
Знайсці ўсе перастаўленыя радкі дадзенага радка ў матрыцы

Касмічная складанасць

O (N) дзе "N" - колькасць элементаў у масіве. Паколькі мы выкарыстоўвалі масіў для захоўвання ўваходных дадзеных і HashMap, які збіраецца захоўваць N элементаў. Такім чынам дасягаецца лінейная складанасць прасторы.