sub array များသည်မူလခင်းကျင်းချက်နှင့်တူညီသည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Databricks fab Honeywell PayU ရင်ပြင် Teradata Yandex
အခင်းအကျင်း hash တားဆီးခြင်း လျှော Window

ပြProbleနာဖော်ပြချက်

“ မူရင်းနှင့်တူညီသောကွဲပြားခြားနားသောဒြပ်စင်များရှိသည့် subarrays များကိုရေတွက်ပါ အခင်းအကျင်း"သင်ကတစ် ဦး ကိန်းစစ်ခင်းကျင်းပေးထားကြသည်ဖော်ပြသည်။ အဆိုပါပြstatementနာကြေညာချက်မူရင်းခင်းကျင်းထဲမှာပစ္စုပ္ပန်အဖြစ်ကွဲပြားသောဒြပ်စင်များပါရှိသည် Sub- Array ကို၏စုစုပေါင်းအရေအတွက်ကထွက်ရှာရန်မေးတယ်။

နမူနာ

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

ရှင်းလင်းချက် - Sub-ခင်းကျင်း⇒ {2, 1, 3}, {1, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 2} နှင့် {2, 1, 3, 2 , 3} မူရင်းခင်းကျင်းအဖြစ်ကွဲပြားသောဒြပ်စင်များပါရှိသည်။

sub array များသည်မူလခင်းကျင်းချက်နှင့်တူညီသည်

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

ရှင်းလင်းချက်: Sub-ခင်းကျင်း⇒ {3, 4, 1, 2}, {4, 3, 4, 1, 2}, {2, 4, 3, 4, 1} နှင့် {2, 4, 3, 4, 1 , 2} မူရင်းခင်းကျင်းအဖြစ်ကွဲပြားသောဒြပ်စင်များပါရှိသည်။

subarrays အရေအတွက်ကိုတွက်ချက်ရန် Algorithm သည်မူရင်းခင်းကျင်းခြင်းနှင့်တူညီသောကွဲပြားခြားနားသောအရာများရှိသည်

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.

ရှင်းလင်းချက်

ငါတို့ပေးထားတယ် ကိန်း array, မူရင်းခင်းကျင်းပြသထားသည့်ကွဲပြားသောဒြပ်စင်များပါ ၀ င်သည့် sub-arrays စုစုပေါင်းအရေအတွက်ကိုရှာဖွေရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်။ ဒီအတွက်ငါတို့သုံးမယ် တားဆီးခြင်း။ ဤကုဒ်ကိုဖြေရှင်းရန်ထိရောက်သောနည်းလမ်းဖြစ်သည်။

a) ကြေညာပါ မြေပုံ။ ကျွန်ုပ်တို့သည် array တစ်ခုလုံးကိုဖြတ်သန်းသွားပြီး element တစ်ခုစီကို ၁ ကြိမ်သာရှိသောမြေပုံထဲသို့ထည့်တော့မည်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည် element တစ်ခုစီ၏ကြိမ်နှုန်းကိုမရေတွက်ချင်သောကြောင့်ဖြစ်သည်။ ပေးထားသောခင်းကျင်းခြင်းတွင်ထူးခြားသောသော့အရေအတွက်မည်မျှရှိသည်ကိုသိရန်သာဖြစ်သည်။ မြေပုံ၏အရွယ်အစားကို k အဖြစ်ပြောင်းလဲပြီးမြေပုံကိုရှင်းလင်းပါမည်။

ကျနော်တို့ခင်းကျင်းတစ်ခုလုံးကိုဖြတ်သန်းသွားမယ်။ သို့သော်၎င်းမတိုင်မီ output ၏တန်ဖိုးကို right နှင့် maxsa ဟုသတ်မှတ်သည်။ သုညမှ စ၍၊ sub-ခင်းကျင်းမှုကိုရှာရန် loop တစ်ခုအတွင်းသို့ ထပ်မံ၍ ၀ င်ရောက်မည်။ ညာဘက်သည် n ထက်ငယ်သည်။ maxsa သည် k ထက်နည်းသည်။ အခုဆိုရင် array element ကိုထည့်လိုက်ပြီးသူ့ရဲ့ကြိမ်နှုန်းကို ၁ နဲ့မြှောက်မယ်။ လက်ရှိ element ကကြိမ်နှုန်း ၁ လားဆိုတာစစ်ဆေးပါလိမ့်မယ်။ ဒါမှမဟုတ်ရင်အဲဒါကိုမှန်တယ်လို့တွေ့ရှိခဲ့ရင်တန်ဖိုးကိုတိုးလိုက်မယ်။ maxsa ၏။

ထဲကမှလာမယ့်ပြီးနောက် နေစဉ်ကွင်းဆက်၊ ခင်ဗျားက maxsa ရဲ့တိုးတဲ့တန်ဖိုးကိုရလိမ့်မယ်။ အကယ်လို့ k နဲ့ညီမယ်ဆိုရင်၊ output ကို n-right +1 ကို update လုပ်ပါ။ ကျနော်တို့ထားပြီး element ကို၏တန်ဖိုးကိုမြေပုံထဲသို့သွင်းထားသကဲ့သို့။ ယခုကျွန်ုပ်တို့သည်၎င်း၏ကြိမ်နှုန်းကို 1 ဖြင့်လျှော့ချပြီး arr [left] တန်ဖိုးသည် 0 နှင့်ညီမျှပြီး Maxsa တန်ဖိုးကိုလျော့သွားလိမ့်မည်။ maxsa တန်ဖိုး k ကိုရှာသည့်အခါတိုင်းကျွန်ုပ်တို့သည် output တန်ဖိုးကို update လုပ်လိမ့်မည်။

ကုဒ်

C ++ ကုဒ်သည်မူလခင်းကျင်းချက်နှင့်တူညီသောကွဲပြားခြားနားသောဒြပ်စင်များရှိသည့် subarrays များကိုရေတွက်ရန်ဖြစ်သည်

#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

Subray များ Count to Java code သည်မူရင်းခင်းကျင်းမှုနှင့်တူညီသောကွဲပြားခြားနားသောဒြပ်စင်များရှိခြင်း

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်တော်တို့ဟာ array ကိုဖြတ်ကျော်ပြီး linear အချိန်ရှုပ်ထွေးမှုကိုအောင်မြင်စေတဲ့ HashMap ကိုသုံးပြီးကတည်းက။

အာကာသရှုပ်ထွေးမှု

အို (N) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည် input ကိုသိမ်းဆည်းရန် array နှင့် N element များကိုသိုလှောင်မည့် HashMap ကို အသုံးပြု၍ ဖြစ်သည်။ ထို့ကြောင့် linear အာကာသရှုပ်ထွေးအောင်မြင်သည်။