subguay အရှည်ဆုံး K သည်ကွဲပြားသောဒြပ်စင်များမပါရှိခြင်း


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Citadel ဒေလီ Facebook က Microsoft က Samsung Yandex
အခင်းအကျင်း hash လျှော Window

ပြKနာ“ K ကွဲပြားခြားနားသောဒြပ်စင်များမပါသည့်အရှည်ဆုံး subarray” တွင်သင်၌ရှိသည်ဟုဆိုပါသည် အခင်းအကျင်း of ကိန်း, ပြstatementနာဖော်ပြချက်သည် k ကွဲပြားခြားနားသော element များထက်မပိုသောအရှည်ဆုံး sub-array ကိုရှာဖွေရန်တောင်းဆိုသည်။

နမူနာsubguay အရှည်ဆုံး K သည်ကွဲပြားသောဒြပ်စင်များမပါရှိခြင်း

arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5}
k=3
2, 1, 2, 0

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

k ကွဲပြားသောဒြပ်စင်နှင့်အတူအရှည်ဆုံး Sub-ခင်းကျင်း (2, 1, 2, 0)

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

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

k ကွဲပြားသောဒြပ်စင်နှင့်အတူအရှည်ဆုံး Sub-ခင်းကျင်း (3, 4)

algorithm

  1. ဒြပ်စင်တစ်ခုစီ၏အရေအတွက်ကိုတိုး။ ထိန်းသိမ်းထားပါ
  2. 0 ကနေစ။ သည် k ထက်ကြီးလာသည်အထိကွဲပြားသောဒြပ်စင်များစွာကိုထိန်းသိမ်းထားသည်။
  3. အကယ်၍ count သည် k ထက်ကြီးလျှင် element များ၏ရေတွက် (စမှတ်) ကိုစတင်လျှော့ချပါ။
  4. ကျွန်ုပ်တို့သည်ထပ်မံမရောက်မချင်းရေတွက်ခြင်းကိုဆက်လက်ဖယ်ရှားပေးပါ။ k element များသည်လည်း Sub-ခင်းကျင်းမှု၏စမှတ်ကိုတိုးမြှင့်သည်။
  5. အရှည်ဆုံး sub-array အရှည်ကိုစစ်ဆေးခြင်းအားဖြင့် array element အညွှန်းအရသိရသည်အဆုံးကို update ။
  6. အဆုံးသတ်မှစတင်သည့်ခင်းကျင်းသည့်ပုံစံကိုပုံနှိပ်ပါ။

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

ကျွန်တော်တို့ဟာကိန်းဂဏန်းစုစုပေါင်းကိုပေးပြီးပါပြီ။ k ကွဲပြားတဲ့ element တွေထက်မကတဲ့ array ထဲမှာအရှည်ဆုံး sub-array ကိုရှာဖို့ကျွန်တော်တို့တောင်းဆိုခဲ့တယ်။ ငါတို့ကဲ့သို့အလားတူနည်းလမ်းကိုသုံးမည် ဟေး။ ကျွန်ုပ်တို့သည်အရှည်ဆုံး sub-array ကိုရှာဖွေရန်လိုအပ်သော်လည်း element တစ်ခုစီ၏အရေအတွက်ကိုဆက်လက်တိုးမြှင့်ရမည်။ ဒါကြောင့်ကျွန်တော်တို့ဟာ sub-array ရဲ့စမှတ်နှင့် sub-array ရဲ့အဆုံးမှာမျက်လုံးကိုထိန်းသိမ်းထားရမယ်။ ဒါကြောင့်ကျွန်တော်တို့ကပေးထားတဲ့ k element တွေထက်မက start-end မှ sub-array ကို print ထုတ်ပါမယ်။

ထို့အပြင်မည်သည့်နံပါတ်သည် than ထက် ပို၍ မကြီးသင့်ကြောင်းသေချာစေသောအရာ၏အရေအတွက်ကိုထိန်းသိမ်းရန်လိုအပ်သည်။ ဥပမာတစ်ခုယူကြစို့။

Arr [] = {4, 3, 5, 2, 1, 2, 0, 4, 5}, k = 3 =

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

array တစ်ခုမှ 4, 3 and 5 ကိုစဉ်းစားလျှင် i = 2, curr = 3၊ နောက် element တစ်ခုသို့သွားလျှင် curr ကို 4 အဖြစ်ရလျှင် 2 သည် XNUMX ကို sub-array ၏စတင်အမှတ်အဖြစ်ယူထားသင့်သည်။ ကျနော်တို့ distinct ကွဲပြားဒြပ်စင်ထက်ပိုမိုတွေ့ရှိသည်အထိသွား။

ကုဒ်

C ++ code သည် K ကွဲပြားခြားနားသောဒြပ်စင်များမပါသည့်အရှည်ဆုံး subarray ကိုရှာရန်ဖြစ်သည်

#include<iostream>
#include<unordered_map>
using namespace std;

void getLongestSub(int arr[], int n, int k)
{
    unordered_map<int, int> count;

    int start = 0, endp = 0, curr = 0, left = 0;
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
        if (count[arr[i]] == 1)
            curr++;
        while (curr > k)
        {
            count[arr[left]]--;

            if (count[arr[left]] == 0)
                curr--;

            left++;
        }
        if (i - left + 1 >= endp - start + 1)
        {
            endp = i;
            start = left;
        }
    }
    for (int i = start; i <= endp; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getLongestSub(arr, n, k);
    return 0;
}
2 1 2 0

ဂျာဗားကုဒ်သည် K ကွဲပြားခြားနားသောဒြပ်စင်များမပါသည့်အရှည်ဆုံး subarray ကိုရှာရန်ဖြစ်သည်

import java.util.*;

class longestSubArray
{
    public static void getLongestSub(int arr[], int n, int k)
    {
        int[] count = new int[7];
        int start = 0, end = 0, curr = 0, left = 0;
        for (int i = 0; i < n; i++)
        {
            count[arr[i]]++;
            if (count[arr[i]] == 1)
                curr++;

            while (curr > k)
            {
                count[arr[left]]--;

                if (count[arr[left]] == 0)
                    curr--;
                left++;
            }
            if (i - left + 1 >= end - start + 1)
            {
                end = i;
                start = left;
            }
        }
        for (int i = start; i <= end; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String args[])
    {
        int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
        int n = arr.length;
        int k = 3;
        getLongestSub(arr, n, k);
    }
}
2 1 2 0

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

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ hashmap ကိုအသုံးပြုခြင်းအားဖြင့်ကျွန်ုပ်တို့ (O) အချိန်အတွင်းထည့်သွင်းရန်၊ ဖျက်ရန်နှင့်ရှာဖွေရန်ခွင့်ပြုထားသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ အဆိုးဆုံးမှာကျွန်ုပ်တို့သည်အရာဝတ္ထုအားလုံးကိုသိမ်းထားရန်လိုလိမ့်မည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။