Пребройте подредове, имащи общо различни елементи, същите като оригиналния масив  


Ниво на трудност M
Често задавани в Амазонка Датчици за данни Fab Honeywell PayU Площад Терадата Yandex
Array Хашиш хеширане Плъзгащ се прозорец

Декларация за проблема  

„Пребройте подчините, които имат общо различни елементи, същите като оригиналните масив”Заявява, че сте получили цяло число масив. Изявлението за проблем иска да открие общия брой подмасиви, които съдържат всички отделни елементи, присъстващи в оригинален масив.

Пример  

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 знака

Декларирайте а карта. Ще преминем през целия масив и ще поставим всеки елемент в картата само с честота, която е 1. Тъй като не искаме да броим честотата на всеки елемент. Това е само за да се знае колко уникални ключове присъстват в даден масив. Ще съхраним размера на картата в променливата k и ще изчистим картата.

Ще преминем през целия масив. Но преди това задаваме стойността на изхода, вдясно и maxsa на 0. Започвайки от 0, ще влезем отново в цикъл в търсене на подмасив, докато вдясно е по-малко от n и maxsa е по-малко от k. Сега ще поставим елемента на масива и ще увеличим неговата честота с 1. Ще проверим дали текущият елемент има честота 1. Или просто го актуализираме до повече от това, ако се установи, че е истина, тогава увеличете стойността на maxsa.

След като излезе от докато цикъл, ще имате увеличена стойност на maxsa, ако е равна на k, след това актуализирайте изхода на n-дясно +1. Както вече поставихме стойностите на елемента масив в картата. Сега ще намалим честотата му с 1 и ще проверим дали arr [лявата] стойност е равна на 0 и ще намалим максималната стойност. Всеки път, когато намерим стойността на 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

Анализ на сложността  

Сложност във времето

НА) където "Н" е броят на елементите в масива. Тъй като сме обходили масива и сме използвали HashMap, което ни е накарало да постигнем линейна времева сложност.

Вижте също
Намерете всички преместени редове от даден ред в матрица

Сложност на пространството

НА) където "Н" е броят на елементите в масива. Тъй като използвахме масив за съхранение на входа и HashMap, който ще съхранява N елемента. По този начин се постига линейна сложност на пространството.