k Distinct နံပါတ်များဖြင့်အသေးဆုံး Subarray


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Google
အခင်းအကျင်း hash လျှော Window ညွှန်ပြချက်နှစ်ခု

ဆိုတော့မင်းမှာကိန်းပြည့်ရှိတယ် အခင်းအကျင်း နှင့်နံပါတ် k ။ အဆိုပါပြstatementနာကိုကြေညာချက်အားလုံးပါဝင်နိုင်အကွာအဝေး (l, r) ၏အသေးငယ်ဆုံး sub- ခင်းကျင်းထွက်ရှာဖွေရန်မေးတယ်, ထိုကဲ့သို့သောလမ်းအတွက်ကြောင့်အသေးငယ်ဆုံး sub- ခင်းကျင်းထဲမှာပစ္စုပ္ပန် k ကွဲပြားနံပါတ်များကိုရှိပါတယ်။

နမူနာ

input:

{1, 2, 2, 3, 4, 5, 5}

= = ၄

output:

2, 4

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

{2, 3, 4} သည် 2 မှစပြီးအသေးငယ်ဆုံး sub-array ဖြစ်သည်nd အညွှန်းကိန်း 4th ie ဆိုလိုသည်မှာ 3 ကွဲပြားသောဒြပ်စင်နှင့်အတူအညွှန်းကိန်း။

input:

{2, 5, 6, 7}

= = ၄

output:

2, 3

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

{2, 5} သည်ဒုတိယအညွှန်းကိန်းမှကိန်းဂဏန်း ၃ ခုအထိအငယ်ဆုံးသောအခွဲဖြစ်သည်။ ကွဲပြားခြားနားသောဒြပ်စင် ၂ ခုရှိသည်။

algorithm

  1. ကွဲပြားသော element ကို 0 နှင့်ဘယ်ဘက်နှင့်ညာဘက်ခြမ်း -1 သို့ထားပါ။
  2. ခင်းကျင်းဖြတ်သန်းသွားသော
  3. အကယ်၍ ကွဲပြားသောဒြပ်စင်တစ်ခုမျှပေးထားသောနံပါတ် k ထက်နည်းလျှင်ညာဘက်ခြမ်းကို ၁ တိုးခြင်း။
  4. ထို့နောက် count ကိုတိုး။ array element ၏ကြိမ်နှုန်းကိုသိမ်းဆည်းပါ မြေပုံ.
  5. ကွဲပြားသောဒြပ်စင်များသည်ပေးထားသောအရေအတွက် k နှင့်ညီမျှပြီးဤသို့ဖွဲ့စည်းထားသောအရှည်သည်ယခင်ကအသစ်တင်ထားသောအရှည်ထက်သေးငယ်လျှင်၊
  6. ကွဲပြားခြားနားသောဒြပ်စင်များ၏အရေအတွက်သည် k ထက်နည်းသည်ကိုတွေ့ရှိလျှင်ချိုးပါ။
  7. ကွဲပြားခြားနားသော element များ၏အရေအတွက်သည် k နှင့်ညီမျှမှုရှိမရှိစစ်ဆေးပါ၊ ထို့နောက်ညာဘက်ခြမ်းကိုမြှင့်ပါ။
  8. ကွဲပြားသောဒြပ်စင်များသည်ပေးထားသောအရေအတွက် k နှင့်ညီမျှပြီးဤသို့ဖွဲ့စည်းထားသောအရှည်သည်ယခင်ကအသစ်တင်ထားသောအရှည်ထက်သေးငယ်လျှင်၊
  9. ဒြပ်စင်၏ကြိမ်နှုန်းသည် ၁ ဖြစ်မဖြစ်စစ်ဆေးပါ၊ ထိုဒြပ်စင်ကိုမြေပုံမှဖယ်ရှားပါ၊ သို့မဟုတ်ထိုဒြပ်စင်၏ကြိမ်နှုန်း၏အရေအတွက်ကိုလျော့နည်းစေပါ။
  10. ဘယ်ဘက်ခြမ်းကို 0 နှင့်ညာဘက်ခြမ်း n နှင့်ညီမျှသည်ဆိုပါကမမှန်ကန်ကြောင်းကိုဆိုလိုသည်။
  11. ကျန်ရှိသောဘယ်ဘက်နှင့်ညာဖက်တန်ဖိုးများကိုပုံနှိပ်ပါ။

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

Array ကိုဖြတ်သန်းနေစဉ် array element များအကြိမ်ရေကိုသိုလှောင်သိမ်းဆည်းပါ။ array element တစ်ခုချင်းစီကိုရွေးပါ။ ၎င်း array ၏ကြိမ်နှုန်းကိုရေတွက်ရန်နှင့်သိုလှောင်ရန်လိုအပ်သည်ထက်၎င်းသည် k ထက်လျော့နည်းကြောင်းတွေ့ရှိပါကမြေပုံအရွယ်အစားသည် k ထက်လျော့နည်းမှုရှိမရှိစစ်ဆေးပါ။ မြေပုံအရွယ်အစားသည် k (ကွဲပြားခြားနားသောဒြပ်စင်နံပါတ်) ဖြစ်ပြီးလက်ရှိအရှည်သည်ယခင်ခင်းကျင်းထားသည့်အတိုင်းအတာထက်နည်းသည်၊ ထို့နောက်ကျွန်ုပ်တို့သည်ဘယ်ဘက်နှင့်ညာဘက်ခြမ်းကိုအသစ်ပြောင်းမည်။ မြေပုံတစ်ခုလုံးတစ်ချိန်ကဖြတ်သန်းသွားသည်အထိဤအရာအားလုံးသည်ကွင်းဆက်တစ်ခုအတွင်းသို့ရောက်သွားလိမ့်မည်။

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

ဘယ်ဘက်ခြမ်းညွှန်ပြသူသည် ၀ ဖြစ်သည်၊ ညာဘက်ခြမ်းတွင် n ကိုရှာပါကစစ်ခင်းကျင်းမှုကိုဖြတ်သန်းပြီးနောက်၎င်းသည်မမှန်ကန်တဲ့ k ဖြစ်သည်။ ကျန်သည်မှာအသေးငယ်ဆုံး sub-ခင်းကျင်းမှု၏အစနှင့်အဆုံးသတ်ဖြစ်မည့်ဘယ်ဘက်နှင့်ညာဘက်ခြမ်း၏ညွန်ကြားချက်၏တန်ဖိုးကိုပုံနှိပ်ပါ။

အကောင်အထည်ဖော်ရေး

အသေးဆုံး Subarray အတွက် C ++ အစီအစဉ်တွင် D Distinct နံပါတ်များပါ ၀ င်သည်

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

အသေးဆုံး Subarray အတွက် k Distinct နံပါတ်များအတွက် Java ပရိုဂရမ်

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

အသေးဆုံး Subarray အတွက် Analysis ကွဲပြားသောနံပါတ်များနှင့်အတူရှုပ်ထွေးမှုဆန်းစစ်ခြင်း

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။