Ümumilikdə fərqli elementləri orijinal sıra ilə eyni olan subarraysları sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Verilənlər bazası Fab Honeywell PayU kvadrat Teradata Yandex
Geyim Sükut Hashing Sürüşmə pəncərəBaxılıb 42

Problem bəyanat

“Orijinal ilə eyni fərqli elementləri olan subarraysları sayın array”Sizə bütöv bir sıra verildiyini bildirir. Problem ifadəsi, orijinal bir massivdə olduğu kimi bütün fərqli elementləri ehtiva edən alt dizilərin ümumi sayını tapmağı xahiş edir.

misal

arr[] = {2, 1, 3, 2, 3}
5

İzahat: Alt sıra ⇒ {2, 1, 3}, {1, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 2} və {2, 1, 3, 2 , 3} bütün fərqli elementləri orijinal sıra kimi ehtiva edir.

Ümumilikdə fərqli elementləri orijinal sıra ilə eyni olan subarraysları sayınPin

arr[] = {2, 4, 3, 4, 1, 2}
4

İzahat: Alt sıra ⇒ {3, 4, 1, 2}, {4, 3, 4, 1, 2}, {2, 4, 3, 4, 1} və {2, 4, 3, 4, 1 , 2} bütün fərqli elementləri orijinal sıra kimi ehtiva edir.

Orijinal massivlə eyni cəmi fərqli elementləri olan subarları saymaq üçün alqoritm

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.

Izahat

Biz verdik tam array, orijinal bir massivdə olduğu kimi bütün fərqli elementləri ehtiva edən alt dizilərin ümumi sayını tapmaq istənir. Bunun üçün istifadə edəcəyik Hashing. Bu kodu həll etmək üçün səmərəli bir yanaşmadır.

Bəyan edin a xəritə. Bütün massivi keçib hər elementi xəritəyə yalnız 1 olan bir tezliklə qoyacağıq. Çünki hər bir elementin tezliyini saymaq istəmirik. Bu, yalnız müəyyən bir massivdə nə qədər unikal düymələrin olduğunu bilməkdir. Xəritə ölçüsünü k dəyişənində saxlayacağıq və xəritəni təmizləyəcəyik.

Bütün massivi keçəcəyik. Ancaq bundan əvvəl, sağ və maxsa çıxış dəyərini 0-a təyin etdik. 0-dan başlayaraq alt sıra axtararaq döngəyə yenidən daxil olacağıq, sağ n-dən, maxsa isə k-dan azdır. İndi sıra elementini qoyub tezliyini 1 artıracağıq. Hazırkı elementin 1 tezliyinə sahib olub olmadığını yoxlayacağıq. Və ya daha doğrusunu yenilədik, doğru olduğu təqdirdə dəyəri artırın. maxsa.

Çıxdıqdan sonra döngə zamanı, artan maxsa dəyərinə sahib olacaqsınız, əgər k-ya bərabərdirsə, nəticəni n-right +1-ə yeniləyin. Artıq sıra elementinin dəyərlərini xəritəyə qoyduğumuz kimi. İndi tezliyini 1-ə endirəcəyik və arr [sol] dəyərinin 0-a bərabər olub olmadığını yoxlayacağıq və maxsa dəyərini azaltacağıq. Maxsa dəyərini k-ya nə qədər tapsaq, çıxış dəyərini də yeniləyəcəyik.

Kodu

C ++ kodu, orijinal massivlə eyni cəmi fərqli elementlərə sahib subarları saymaq üçün

#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

Cəmi fərqli elementləri orijinal massivlə eyni olan alt cədvəlləri saymaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) hara "N" massivdəki elementlərin sayıdır. Dizini keçdiyimiz və xətti zaman mürəkkəbliyinə nail olmağımızı təmin edən HashMap istifadə etdiyimiz üçün.

Kosmik Mürəkkəblik

O (N) hara "N" massivdəki elementlərin sayıdır. Çünki biz girişi saxlamaq üçün bir sıra və N elementi saxlayacaq bir HashMap istifadə etdik. Beləliklə, xətti kosmik mürəkkəblik əldə edilir.

Translate »