મૂળ એરે સમાન કુલ વિશિષ્ટ તત્વો ધરાવતા સબએરેય્સની ગણતરી કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન ડેટાબેક્સ ફેબ હનીવેલ પે સ્ક્વેર તેરાદાતા યાન્ડેક્ષ
અરે હેશ હેશિંગ બારણું વિંડો

સમસ્યા નિવેદન

“મૂળ જેટલા જ અલગ વિશિષ્ટ તત્વો ધરાવતા સબએરાઇઝની ગણતરી કરો એરે”જણાવે છે કે તમને પૂર્ણાંક એરે આપવામાં આવે છે. સમસ્યાનું નિવેદન પેટા-એરેની કુલ સંખ્યા શોધવા માટે પૂછે છે જેમાં મૂળ એરેમાં હાજર બધા વિશિષ્ટ તત્વો હોય છે.

ઉદાહરણ

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 original મૂળ એરે તરીકે બધા વિશિષ્ટ તત્વો ધરાવે છે.

મૂળ એરે સમાન કુલ વિશિષ્ટ તત્વો ધરાવતા સબએરેય્સની ગણતરી કરો

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 original મૂળ એરે તરીકે બધા વિશિષ્ટ તત્વો ધરાવે છે.

મૂળ એરે સમાન કુલ વિશિષ્ટ તત્વો ધરાવતા સબમરીને ગણતરી માટે અલ્ગોરિધમ

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 આવર્તન સાથે નકશામાં મુકીશું. કારણ કે આપણે દરેક તત્વની આવર્તન ગણતરી કરવા માંગતા નથી. આપેલ એરેમાં કેટલી અનન્ય કીઓ હાજર છે તે જાણવા માટે જ આ છે. આપણે નકશાના કદને વેરિયેબલ કેમાં સંગ્રહિત કરીશું અને નકશાને સાફ કરીશું.

અમે સમગ્ર એરેને પસાર કરીશું. પરંતુ તે પહેલાં, આપણે આઉટપુટ, જમણી અને મેક્સાની કિંમત 0 પર સેટ કરી છે, 0 થી શરૂ કરીને, આપણે ફરીથી પેટા-એરેની શોધમાં લૂપમાં દાખલ કરીશું, જ્યારે જમણો n કરતા ઓછો છે અને મેક્સસા k કરતા ઓછું છે. હવે, આપણે એરે એલિમેન્ટ મૂકીશું અને તેની ફ્રીક્વન્સી 1. દ્વારા વધારીશું. આપણે તપાસ કરીશું કે હાલના તત્વની આવર્તન 1 છે કે નહીં. અથવા આપણે તેને હજી વધુ અપડેટ કર્યું છે, જો તે સાચું જણાયું છે, તો મૂલ્યમાં વધારો. મેક્સા ની.

ની બહાર આવ્યા પછી જ્યારે લૂપ, તમારી પાસે મેક્સસાનું વધારાનું મૂલ્ય હશે, જો તે k ની બરાબર હોય, તો આઉટપુટને n-right +1 પર અપડેટ કરો. આપણે પહેલેથી જ નકશામાં એરે એલિમેન્ટની કિંમતો મૂકી છે. હવે આપણે તેની આવર્તન 1 દ્વારા ઘટાડીશું, અને તપાસો કે એઆર [ડાબી] કિંમત 0 ની બરાબર છે અને મેક્સસા મૂલ્યમાં ઘટાડો. જ્યારે પણ અમને મેક્સસાથી 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

મૂળ એરે સમાન કુલ વિશિષ્ટ તત્વો ધરાવતા સબએરેય્સની ગણતરી માટે જાવા કોડ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણે એરેને ઓળંગી ગયા છે અને હેશમેપનો ઉપયોગ કર્યો છે જેણે અમને રેખીય સમયની જટિલતા પ્રાપ્ત કરી છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણે ઇનપુટ સંગ્રહ કરવા માટે એરે અને હેશમેપનો ઉપયોગ કર્યો છે જે એન તત્વોને સંગ્રહિત કરશે. આમ રેખીય અવકાશ જટિલતા પ્રાપ્ત થાય છે.